Aashish Panchal

Posted on

# Dijkstra Binary Heap PQ

Last program of Java Script

``````    class weightedGraph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
console.log(` ->   \${vertex}`)
}

addEdge(vertex1,vertex2, weight) {
this.adjacencyList[vertex1].push({node: vertex2, weight});
this.adjacencyList[vertex2].push({node :vertex1, weight});
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
for(let vertex in this.adjacencyList) {
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) {
for(let neighbor in this.adjacencyList[smallest]) {
// find neighboring node
let nextNode = this.adjacencyList[smallest][neighbor];
// 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());
}
}

class priorityQueue {
constructor() {
this.values = []
}
enqueue(val, priority) {
let newNode = new Node(val, priority)
this.values.push(newNode);
this.bubbleUp();
}

bubbleUp() {
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx > 0) {
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element.priority <= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}

dequeue () {
const min = this.values[0];
const end = this.values.pop();
if(this.values.length > 0) {
this.values[0] = end;
this.sinkDown()
}
return min;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while(true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild,rightChild;
let swap = null;
if(leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if(leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if(rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if(
(swap === null && rightChild.priority < element.priority)
||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIdx;
}
}

if(swap === null) break;
this.values[idx] = this.values[swap]
this.values[swap] = element;
}
}
}

class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}

var graph = new weightedGraph();
console.log("<---value--->")
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")
console.log("<---AddEdg value--->")
graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "E", 3);
graph.addEdge("C", "D", 2);
graph.addEdge("C", "F", 4);
graph.addEdge("D", "E", 3);
graph.addEdge("D", "F", 1);
graph.addEdge("E", "F", 1);
console.log("<---Dijkstra's value--->")
graph.Dijkstra("A", "E");
``````