Table of Contents
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’s 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.
| Vertex | Shortest Distance from A |
| A | 0 |
| B | Infinity |
| C | Infinity |
| D | Infinity |
| E | Infinity |
| F | Infinity |
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
| Vertex | Shortest Distance from A |
| A | 0 |
| B | 4 |
| C | 2 |
| D | 4 |
| E | 6 |
| F | 5 |
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
- dequeue a vertex from the priority queue
- 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");
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’s 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");
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.
Source: https://www.codeunderscored.com/dijkstras-algorithm-in-javascript/
