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.
finding the shortest path from A to E
finding the shortest path from A to E
VertexShortest Distance from A
A0
BInfinity
CInfinity
DInfinity
EInfinity
FInfinity
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

VertexShortest Distance from A
A0
B4
C2
D4
E6
F5
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(){
		this.adjacencyList ={}
	}
	addVertex(vertex){
	if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] =[];
	}
	addEdge(vertex1, vertex2, weight){
	this.adjacencyList[vertex1].push({node:vertex2, weight})
	this.adjacencyList[vertex2].push({node:vertex1,weight})
	}
}

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(){
		this.adjacencyList ={}
	}
	addVertex(vertex){
	if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] =[];
	}
	addEdge(vertex1, vertex2, weight){
	this.adjacencyList[vertex1].push({node:vertex2, weight})
	this.adjacencyList[vertex2].push({node:vertex1,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){
				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){
			  	for(let neighbor in this.adjacencyList[smallest]){
					// find neighboring node
					let nextNode = this.adjacencyList[smallest][neighbor];
					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.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")


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

graph.Dijkstra("A", "E");
Using Dijkstra to find the shortest path from A to E
Using Dijkstra to find the shortest path from A to 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(){
		this.adjacencyList ={}
	}
	addVertex(vertex){
	if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] =[];
	}
	addEdge(vertex1, vertex2, weight){
	this.adjacencyList[vertex1].push({node:vertex2, weight})
	this.adjacencyList[vertex2].push({node:vertex1,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){
				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){
			  	for(let neighbor in this.adjacencyList[smallest]){
					// find neighboring node
					let nextNode = this.adjacencyList[smallest][neighbor];
					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[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;
        idx =swap;
        }

    }
}

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


var graph =new WeightedGraph()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")


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


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

improved Dijkstra to find shortest path from A to E
improved Dijkstra to find the shortest path from A to E

Conclusion

In this article, we have looked at Graphs as collections of vertices connected by edges. There are various ways of representing graphs, and the obvious ones include using adjacency lists, adjacency matrices, and quite a few other forms.

When Graphs contain weights and directions, they form cycles. Just like trees, graphs can be traversed using BFS and DFS. Shortest path algorithms like Dijkstra can be altered using a heuristic to achieve better results like those with A*. There are numerous applications of Dijkstra’s algorithms ranging from biology, computer networks, finding the shortest paths both via road networks and when flying from one destination to another.

You may also like

Leave a Comment

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More