Home Web DevelopmentJavaScript Dijkstra’s Algorithm in JavaScript

# Dijkstra’s Algorithm in JavaScript

Dijkstra’s algorithm is one of the most famous and widely used algorithms responsible for finding the shortest path between two given vertices on a graph. It answers the question, “What’s the fastest way to get from point A to point B?”

The algorithm was developed by Edsger Dijkstra, a Dutch programmer, physicist, essayist, and generally an all-around smarty-pants. By a substantial dimension, he helped advance the field of computer science from an “art” to an academic discipline. In fact, most of his discoveries and algorithms are still commonly used today.

In his own words, during an interview, Edsger claims to have designed what is now famously known as Dijkstra’s algorithm over a cup of coffee with his young fiancee. He is amazed at how a 20-minute job of trying to figure out the shortest path from Rotterdam to Groningen, which generally translated from one city to another city, became the cornerstone of his fame. It is now famously known as the algorithm for finding the shortest path.

### Why is Dijkstra’s practical algorithm?

• GPS -finding the fastest route
• Network routing -finds the open shortest paths for data
• Biology – used to model the spread of viruses among humans
• Airline tickets – finding the cheapest route to your destination

### Finding the shortest path from A to E

The approach

• Every time we look to visit a new node, we pick the node with the smallest known distance to visit first
• Once we’ve moved to the node we’re going to visit, we look at each of its neighbors
• For each neighboring node, we calculate the distance by summing the total edges that lead to the node we’re checking from the starting node.
• If the new total distance to a node is less than the previous total, we store the new shorter distance for that node.
```visited =[];

previous ={
A: null,
B: null,
C: null,
D: null,
E: null,
F: null
}```

Solution: First, start by picking the smallest distance starting at A

```visited =[A, C, B, D,F]

previous ={
A: null,
B: A,
C: A,
D: C,
E: F,
F: D
}```

### A simple Priority Queue

A Priority queue is a kind of data structure that takes in values and their priorities and stores them as an array based on the priority. For instance, if we are storing values with people’s ages, then a person with age 10 will come earlier than one with age 29 on the priority list.

```class PriorityQueue{

constructor(){
this.values =[];
}

enqueue(val, priority){
this.values.push({val, priority});
this.sort()
};

dequeue(){
return this.values.shift();
};

sort(){
this.values.sort((a,b) => a.priority -b.priority);

};
}```

Our sorting, in this case, runs in time complexity of O(N * log(N))

Can we do better?

We sure can! Using a min binary heap. But first, let us focus on Dijkstra’s pseudocode.

### Dijkstra’s Pseudocode

• The function should accept a starting and an ending vertex
• Create an object called distances and set each key to be the same vertex in the adjacency list with a value of infinity, except for the starting vertex, which should have a value of 0.
• After setting a value in the distances object, add each vertex with a priority of infinity to the priority queue, except the starting vertex, which should have a priority of 0 because that’s where we begin.
• Create another object called previous and set each key to be the every vertex in the adjacency list with a value of null
• start looping as long as there is anything in the priority queue
• dequeue a vertex from the priority queue
• if that vertex is the same as the ending vertex – we are done!
• Otherwise, loop through each value in the adjacency list at that vertex
• Calculate the distance to that vertex from the starting vertex
• If the distance is less than what is currently stored in our distances object
• update the distances object with a new lower distance
• update the previous object to contain that vertex
• enqueue the vertex with the total distance from the start node

### Weighted Graph

The following code shows the function WeightedGraph that creates a weighted graph by instantiating an adjacencyList. It also has methods to addVertex and addEdge to a weighted graph.

```class WeightedGraph{

constructor(){
}
}
}
}```

### Implementation of Dijkstra’s algorithm

The implementation of Dijkstra’s algorithm brings together various logics including a PriorityQueue, a WeightedGraph, and the core logic of Dijkstra. Below is the code.

```class PriorityQueue{

constructor(){
this.values =[];
}

enqueue(val, priority){
this.values.push({val, priority});
this.sort()
};

dequeue(){
return this.values.shift();
};

sort(){
this.values.sort((a,b) => a.priority -b.priority);

};
}

class WeightedGraph{

constructor(){
}
}
}

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){
nodes.enqueue(vertex, 0);
distances[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];
}
}
if(smallest || distances[smallest] != Infinity){
// find neighboring node
console.log(nextNode);
// calculate new distance to neighboring node
let candidate =distances[smallest] + nextNode.weight;
let nextNeighbor = nextNode.node;

if(candidate < distances[nextNeighbor]){
// updating new smallest distance to neighbor
distances[nextNeighbor] = candidate;
// updating previous – How we got to neighbor
previous[nextNeighbor] = smallest;
// enqueue in priority queue with new priority
nodes.enqueue(nextNeighbor, candidate);
}
}
}

}
return path.concat(smallest).reverse();
}

}

var graph =new WeightedGraph()

graph.Dijkstra("A", "E");
```

### Improving Dijkstra’s algorithm

Dijkstra’s algorithm is greedy! As a result, it can cause problems! Thus, we can improve this algorithm by adding heuristics, simply the best guess. In this improvement, implementing the priority queue is much faster than the previously used naive algorithm that uses an array. Even though the binary heap itself is stored in an array, it is much efficient than the traditional approach involving sorting the array over and over and picking the minimum value.

```class WeightedGraph{

constructor(){
}
}
}

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){
nodes.enqueue(vertex, 0);
distances[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];
}
}
if(smallest || distances[smallest] != Infinity){
// find neighboring node
console.log(nextNode);
// calculate new distance to neighboring node
let candidate =distances[smallest] + nextNode.weight;
let nextNeighbor = nextNode.node;

if(candidate < distances[nextNeighbor]){
// updating new smallest distance to neighbor
distances[nextNeighbor] = candidate;
// updating previous – How we got to neighbor
previous[nextNeighbor] = smallest;
// enqueue in priority queue with new priority
nodes.enqueue(nextNeighbor, candidate);
}
}
}

}
return 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;
const end = this.values.pop();
if(this.values.length > 0){
this.values =end;
this.sinkDown();
}
return min;

}
sinkDown(){
let idx = 0;
const length = this.values.length;
const element = this.values;
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;
idx =swap;
}

}
}

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

var graph =new WeightedGraph()

graph.Dijkstra("A", "E");

```