Aashish Panchal

Posted on

# Dijkstra First Version

``````class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(val, priority) {
this.values.push({val, priority});
this.sort();
return values
};
dequeue() {
return this.values.shift();
};
sort() {
this.values.sort((a, b) => a.priority - b.priority);
};
}

class weightedGraph {
constructor() {
}
console.log(` ->   \${vertex}`)
}

console.log(` ->   graph.addEdge ("\${vertex1}", "\${vertex2}", \${weight})`)
}

Dijkstra(start, finish) {
const nodes = new PriorityQueue();
const distances = {};
const previous = {};
let path = [] // to return at end
let smallest

// build up initial state
if(vertex === start) {
distances[vertex] = 0;
nodes.enqueue(vertex, 0);
} else {
distances[vertex] = Infinity;
nodes.enqueue(vertex, Infinity);
}
previous[vertex] = null;
}

// As Long as there is Something to visit
while(nodes.values.length) {
smallest = nodes.dequeue().val;
if(smallest === finish) {
// WE ARE DONE
// BUILD UP PATH TO RETURN AT END
while(previous[smallest]) {
path.push(smallest);
smallest = previous[smallest];
}
break;
}
if(smallest || distances[smallest] !== Infinity) {
// find neighboring node
// Calculate new distances to neighboring node
let candidate = distances[smallest] + nextNode.weight;
let nextNeighbor = nextNode.node
if(candidate < distances[nextNeighbor]) {
// Upadating new smallest distance to neighbor
distances[nextNeighbor] = candidate;
// Upadating previous - How we got to neighbor
previous[nextNeighbor] = smallest;
// enqueue in priority queue with new priority
nodes.enqueue(nextNeighbor, candidate);
}
}
}
}
console.log(path.concat(smallest).reverse());
}
}

var graph = new weightedGraph();
console.log("<---value--->")