## DEV Community is a community of 765,064 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Aashish Panchal

Posted on

# Dijkstra Binary Heap PQ

Last program of Java Script

``````    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());
}
}

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--->")