Let’s say from a A to D through B and C we want to find the shortest distance to get from A to D, Assuming those points are not in line but spread on different routes, Dijkstra’s Algorithm says that Move from the starting point ie. A and look for the shortest distance between the adjacent vertex and visit it first then since the destination is unknown use the current total distance and add to the cost of moving from the second current point to the destination and at arrival compute all and donate it to the destination as the total distance taken, repeat for all the routes that leads to the other side and compare all rounds to deduce the shortest distance. seems little abstract right ? let’s see what we mean below. the needed pre-requisite for this task are a Definition of a node, a priority queue and a weighted graph to find the Dijkstra’s Algorithms. Since we had a look at almost all those processes am going to bring back the same codes we covered earlier and chain it with the Dijkstra’s in the weighted graph.
class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
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 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) {
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 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.addVertex('G');
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.addEdge('F', 'G', 1);
graph.Dijkstra('A', 'G');
console.log(graph.Dijkstra('A', 'G'));
No cause for alarm here the code is lengthy but we just repeated the same previous section snippets to help figure out how to build the Dijkstra’s Algorithm. kindly take a look at it and try to make some meaning out of it, you’re not supposed to understand it just at once but little efforts of not giving up yet and practicing will help really understand what is really going on in the above solutions. Read more and keep practicing, Next we will look at Dynamic Programming. Stay Safe 🙂