Solving Dijkstra?s algorithm using JavaScript
In my exploration of data structures and algorithms, I have finally arrived at the famous Dijkstra?s Shortest Path First algorithm (Dijkstra?s algorithm or SPF algorithm for short). Dijkstra?s algorithm is hugely important and can be found in many of the applications we use today (more on this later). As such, beyond just preparing for technical interview questions, it is important to understand. It?s definitely safe to say that not everything clicked for me the first time over; it?s a weighty algorithm with a somewhat unique approach. In an effort to better understand Dijkstra?s algorithm, I decided to devote a whole blog post to the subject. Below we will cover the problem Dijkstra?s algorithm solves, its real-world applications, some key underlying concepts, and finally how to actually implement the algorithm.
What is Dijkstra?s Algorithm?
As the full name suggests, Dijkstra?s Shortest Path First algorithm is used to determining the shortest path between two vertices in a weighted graph.
A simple weighted graph.
The graph above contains vertices of A ? F and edges that possess a weight, that is the numerical value. Dijkstra?s algorithm can be used to calculate the shortest path from A to D, or A to F, or B to C ? any starting point to any ending point. While we can quickly determine the shortest path from A to D, this becomes orders of magnitude harder as the graph scales.
Dijkstra?s algorithm has applications in GPS ? finding the fastest route to a destination, network routing ? finding the shortest open path for data across a network, epidemiology ? modeling the spread of disease, and apps like Facebook, Instagram, Netflix, Spotify, and Amazon that make suggestions for friends, films, music, products, etc. based off of user data.
Graphs
I touched on weighted graphs in the previous section, but we will dive a little deeper as knowledge of the graph data structure is integral to understanding the algorithm. A graph is a non-linear data structure that consists of vertices (or nodes) and edges that connect any two vertices. To reiterate, in the graph above the letters A ? F represent the vertices and the edges are the lines that connect them. In this case, we require a weighted graph meaning the edges possess a magnitude.
Graphs may be represented using an adjacency list which is essentially a collection of unordered lists (arrays) that contain a vertex?s neighboring vertices. In an unweighted graph this would look like the following:
let unweightedAdjacencyList = { “A”: [“B”, “C”], “B”: [“A”, “E”], “C”: [“A”, “D”, “F”], “D”: [“C”, “E”, “F”], “E”: [“B”, “D”, “F”], “F”: [“C”, “D”, “E”]}
In a weighted graph, the adjacency list contains not only a vertex?s neighboring vertices but also the magnitude of the connecting edge. Our adjacency list therefore becomes:
let weightedAdjacencyList = { “A”: [{node: “B”, weight: 4}, {node: “C”, weight: 3}], “B”: [{node: “A”, weight: 4}, {node: “E”, weight: 2}], …}
To build a weighted graph in JavaScript, we first define a class and a constructor function to initialize a new adjacency list.
class WeightedGraph { constructor() { this.adjacencyList = {}; }}
We can now initialize a graph, but we have no ways to add vertices or edges. To add vertices and edges:
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}); }}
The addVertex function takes a new vertex as an argument and, provided the vertex is not already present in the adjacency list, adds the vertex as a key with a value of an empty array. Upon addition, the vertex contains no neighbors thus the empty array.
The addEdge function takes 3 arguments of the 2 vertices we wish to connect and the weight of the edge between them. We then push an object containing the neighboring vertex and the weight into each vertex?s array of neighbors.
We?re now in a position to construct the graph above!
let 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”, 3);graph.addEdge(“B”, “E”, 2);graph.addEdge(“C”, “D”, 3);graph.addEdge(“C”, “F”, 4);graph.addEdge(“D”, “E”, 1);graph.addEdge(“D”, “F”, 1);graph.addEdge(“E”, “F”, 2);
Priority Queues
One other major component is required before we dive into the meaty details of solving Dijkstra?s algorithm; a priority queue. The priority queue data type is similar to that of the queue, however, every item in the queue has an associated priority. The queue is ordered based on descending priorities rather than a first-in-first-out approach. Think triaging patients in the emergency room. Patients with more severe, high-priority conditions will be seen before those with relatively mild ailments.
To create our priority queue class, we must initialize the queue with a constructor and then write functions to enqueue (add a value), dequeue (remove a value), and sort based on priority.
class PriorityQueue { constructor() { this.values = ; } enqueue(value, priority) { this.values.push({value, priority}); this.sort(); } dequeue() { return this.values.shift(); } sort() { this.values.sort((a, b) => a.priority – b.priority); }}
To enqueue, an object containing the value and its priority is pushed onto the end of the queue. The queue is then sorted after every new addition. To dequeue a value from the sorted queue, we use shift to remove the first item in the queue.
At this point, we have covered and built the underlying data structures that will help us understand and solve Dijkstra?s Algorithm.
Approach to Dijkstra?s Algorithm
The code to solve the algorithm is a little unclear without context. It becomes much more understandable with knowledge of the written method for determining the shortest path between vertices. We will, therefore, cover a brief outline of the steps involved before diving into the solution.
Given a starting vertex and an ending vertex we will visit every vertex in the graph using the following method:
- When looking to visit a new vertex, we choose the vertex with the smallest known distance first.
- Once we?ve moved to this vertex, we look at each of its neighbors.
- For each neighboring vertex, we calculate the distance from the starting point by summing all the edges that lead from the start to the vertex in question.
- If the new total distance to the vertex is less than the previous total, we store the new, shorter distance for that vertex.
If you?re anything like me when I first encountered Dijkstra?s algorithm, those 4 steps did very little to advance your understanding of how to solve the problem. Let?s walk through an example with our graph.
Imagine we want to calculate the shortest distance from A to D. To do this we need to keep track of a few pieces of data: each vertex and its shortest distance from A, the vertices we have visited, and an object containing a value of each vertex and a key of the previous vertex we visited to get to that vertex. To begin, the shortest distance from A to A is zero as this is our starting point. We initialize the distances from all other vertices to A as infinity because, at this point, we have no idea what is the shortest distance from A to B, or A to C, or A to D, etc.
For reference, here is our graph again!
We start at A and look at its neighbors, B and C. We record the shortest distance from B to A which is 4. Then we record the shortest distance from C to A and that is 3. Of B and C, A to C is the shortest distance so we visit C next. In our array of visited vertices, we push A and in our object of previous vertices, we record that we arrived at C through A. We now look at the neighbors of C: A, D, and F. We have visited A so we move on to D and F. D is a distance of 6 from A (3+3) while F is a distance of 7 from A (3+4). We record 6 and 7 as the shortest distances from A for D and F, respectively. C is added to the array of visited vertices and we record that we got to D via C and F via C. We now focus on B as it is the vertex with the shortest distance from A that has not been visited. Of B?s neighboring A and E, E has not been visited. We record the shortest distance to E from A as 6, push B into the array of visited vertices, and note that we arrived at E from B. Now the 2 shortest distances from A are 6 and these are to D and E. D is actually the vertex we want to get to, so we?ll look at E?s neighbors. These are D, a distance of 7 from A, and F, a distance of 8 from A (through E). We already have distances of F and D from A recorded (through C). At distances of 7 for F and 6 for D via C, these distances are less than those via E. The shortest distances and routes at which we arrived at those distances will, therefore, remain unchanged. E is added to our array of visited vertices. Last we would visit F and perform the same analysis. The distance of A to D via C and F is 8; larger than our previously recorded distance of 6. The shortest distance from A to D remains unchanged. We note that the shortest distance to arrive at F is via C and push F into the array of visited nodes. With that, we have calculated the shortest distance from A to D.
Now that we can verbalize how the algorithm steps through the graph to determine the solution, we can finally write some code.
Implementing the Algorithm
To begin, we will add a function to our WeightedGraph class called Dijkstra (functions are not usually capitalized, but, out of respect, we will do it here). Dijkstra will take two arguments, a starting vertex and a finishing vertex. Let?s define some variables to keep track of data as we step through the graph.
class WeightedGraph { … Dijkstra(start, finish) { const vertices = new PriorityQueue(); const distances = {}; const previous = {}; let path = ; let smallest; }}
Here we?ve created a new priority queue which will store the vertices in the order they will be visited according to distance. We define a distances object which will hold the shortest distance of a given vertex from the start and a previous object that stores the previous vertex by which we traveled to arrive at a given vertex. The path array will be returned at the end containing the route traveled to give the shortest path from start to finish. Finally, we?ve declared a smallest variable that will come into play later.
In our initial state, we set the shortest distance from each vertex to the start to infinity as currently, the shortest distance is unknown. The exception being the starting vertex, which is set to a distance of zero from the start. We do the same with the priority queue. This gives the starting vertex the highest priority and thus it is where we begin. Finally, we set the previous of each vertex to null to begin.
class WeightedGraph { … Dijkstra(start, finish) { … for(let vertex in this.adjacenctList){ if(vertex === start){ distances[vertex] = 0; vertices.enqueue(vertex, 0); } else { distance[vertex] = Infinity; vertices.enqueue(vertex, Infinity); } previous[vertex] = null; }}
Next, while we have vertices in the priority queue, we will shift the highest priority vertex (that with the shortest distance from the start) from the front of the queue and assign it to our smallest variable.
class WeightedGraph { … Dijkstra(start, finish) { … while(vertices.values.length){ //we just dequeue the value as we don’t need the whole object smallest = vertices.dequeue().value; } }}
If smallest happens to be the finishing vertex, we are done and we build up a path to return at the end.
class WeightedGraph { … Dijkstra(start, finish) { … while(vertices.values.length){ smallest = vertices.dequeue().value; if(smallest === finish) { while(previous[smallest]){ path.push(smallest); smallest = previous[smallest]; } break; } } }}
If not, we need to loop through each neighbor in the adjacency list for smallest. We assign the neighboring vertex, or node, to a variable, nextNode, and calculate the distance to the neighboring node. This is the current distance from smallest to the start plus the weight of nextNode. We assign this value to a variable called candidate. If candidate is smaller than the current distance to that neighbor, we update distances with the new, shorter distance. We must update the previous object to reflect that the shortest distance to this neighbor is through smallest. Finally, we enqueue this neighbor and its distance, candidate, onto our priority queue, vertices.
class WeightedGraph { … Dijkstra(start, finish) { … while(vertices.values.length){ smallest = vertices.dequeue().value; if(smallest === finish) { while(previous[smallest]){ path.push(smallest); smallest = previous[smallest]; } break; } if(smallest || distances[smallest] !== Infinity){ for(let neighbor in this.adjacencyList[smallest]){ let nextNode = this.adjacencyList[smallest][neighbor]; let candidate = distances[smallest] + nextNode.weight; let nextNeighbor = nextNode.node; if(candidate < distances[nextNeighbor]){ distances[nextNeighbor] = candidate; previous[nextNeighbor] = smallest; vertices.enqueue(nextNeighbor, candidate); } } } } }}
That?s the bulk of the logic, but we must return our path. As it stands our path looks like this:
[D, C]
but we want:
[A, C, D]
as this is the shortest path from A to D. To fix the formatting we must concat() A (which is the value ofsmallest) and then reverse the array.
class WeightedGraph { … Dijkstra(start, finish) { … while(vertices.values.length){ smallest = vertices.dequeue().value; if(smallest === finish) { while(previous[smallest]){ path.push(smallest); smallest = previous[smallest]; } break; } if(smallest || distances[smallest] !== Infinity){ for(let neighbor in this.adjacencyList[smallest]){ let nextNode = this.adjacencyList[smallest][neighbor]; let candidate = distances[smallest] + nextNode.weight; let nextNeighbor = nextNode.node; if(candidate < distances[nextNeighbor]){ distances[nextNeighbor] = candidate; previous[nextNeighbor] = smallest; vertices.enqueue(nextNeighbor, candidate); } } } } return path.concat(smallest).reverse() }}
And we?ve done it! We have our solution to Dijkstra?s algorithm. It?s definitely a daunting beast at first, but broken down into manageable chunks it becomes much easier to digest. While a favorite of CS courses and technical interviewers, Dijkstra?s algorithm is more than just a problem to master. It underpins many of the applications we use every day, and may very well find its way into one of your future projects!
