I’ve been reading Grokking Algorithms, which I recommend to anyone new to algorithms. It’s basically the introduction I wish I had a few months ago! The examples in the book are written in Python, so I’d like to share a JavaScript version of Dijkstra’s algorithm. This algorithm uses a directed, weighted graph to determine the “cheapest” path to reach a node.
I’ll be breaking each part into a few steps, with some background information. If you’d prefer to just look at the code, here is the link to the gist.
Background: What is a graph?
A graph is an abstract data type used to model a set of connections. For example, say Bob follows Sarah and Lou on Twitter. Sarah follows Lin. Lou follows Lin and Mark. We can represent these connections using a graph.
Each person is a node and each connection is an edge. Each node can be connected to many other nodes. Graphs can be directed so that each connection is one-way like in this Twitter example — Bob follows Sarah, but Sarah doesn’t follow Bob. Graphs can also be undirected so that connections run both-ways.
Edges in graphs can also be weighted. For example, in the graph below, each weight represents the cost it takes to get from point to point.
The Challenge
Let’s say that you are trying to figure out the cheapest way to reach your destination, as represented by the graph below. The nodes between “start” and “finish” are bridges and roads you can take, and the weights refer to the tolls/gas you’ll have to pay.
Our problem we are trying to solve
At first glance, this looks like things could get hairy! There are many different possible routes to evaluate and compare. And this graph is relatively simple — what if we encounter a more complex problem with more nodes and possible paths?
But Dijkstra’s algorithm takes this intimidating problem and breaks it down, using a few simple steps to reach the final solution. Dijkstra’s algorithm also fits this particular use case well. The graph used to represent the possible paths is directed and acyclic (meaning there are no loops).
The Approach
Implementing the graph
Let’s figure out how to implement the graph in our program. I’ll be using a nested JavaScript object:
const graph = {start: {A: 5, B: 2},A: {C: 4, D: 2},B: {A: 8, D: 7},C: {D: 6, finish: 3},D: {finish: 1},finish: {}};
Each node is represented by the keys in the graph object. Each key has an object for its value, which represents the immediate neighbors and the cost of reaching that neighbor.
For example, node A is connected to nodes C and D. Node A is the “parent” to nodes C and D, and they are the “children” of node A.
Understanding the algorithm
Now let’s outline the main steps in Dijkstra’s algorithm.
- Find the “cheapest” node.
- Update the costs of the immediate neighbors of this node.
- Repeat steps 1 and 2 until you’ve done this for every node.
- Return the lowest cost to reach the node, and the optimal path to do so.
So, if we are beginning at start, the first two nodes we have are A which has a cost of 5, and B which has a cost of 2. B is the cheapest node. These are the only nodes we know of so far besides finish. And since we do not yet know the cost for finish, we’ll set it to Infinity.
That’s already a lot to keep track of, and we’ve only started with the first node! Why don’t we use a new data structure to keep track of the lowest cost to reach each node?
We’ll use an object to keep track of this. So far it looks something like this:
const costs = {A: 5,B: 2,finish: Infinity};
But we don’t just want to know how much it costs to reach the finish node. We want to know the path we need to take to get there! This requires the use of another data structure to keep track of the parent node each node. When a node has many possible parents, we’ll only keep the parent node that leads to the cheapest cost.
This is how we retrace the cheapest path it takes to get from start to finish.
const parents = {A: 'start',B: 'start',finish: null};
Right now we don’t know the full path to reach the finish node yet, since we don’t have the parent of finish.
We also don’t want to waste time going over the same nodes over and over. We want to track which nodes have already been “processed.” “Processed” means we’ve already calculated the cost to reach each of the node’s children.
For this we can simply use an array. Once a node has been processed, we’ll push it to the array.
const processed = [“start”, “A”, “B”];
Okay, so here is the graph we’re working with again.
We want to continue finding the cheapest node and updating the costs of that nodes children. The cheapest node is B, and its children are A (cost of 8) and D (cost of 7). We add those to our costs object, which now looks something like:
console.log(costs)// returns something like{ A: 5,B: 2,D: 9finish: Infinity};
We don’t update the cost of A, since 5 is cheaper than 8. We add D with a value of 9, since the cost to reach B is 2, and the cost to reach D from B is 7, so 7 + 2 = 9.
We also update our processed and parents data structures. We’ll repeat the above steps until we’ve processed all the nodes.
Implementing the algorithm
If this isn’t clear yet, don’t worry, we’re about to step into the code.
First we’ll define a function that given the costs and the processed nodes, will return the cheapest node that hasn’t been processed.
const lowestCostNode = (costs, processed) => {return Object.keys(costs).reduce((lowest, node) => {if (lowest === null || costs[node] < costs[lowest]) {if (!processed.includes(node)) {lowest = node;}}return lowest;}, null);};
Then we’ll define the main function, dijkstra, which will take the initial graph as a parameter. We’ll start off by creating the costs, parents and processed data structures.
const dijkstra = (graph) => {
const costs = Object.assign({finish: Infinity}, graph.start);
const parents = {finish: null};
for (let child in graph.start) { // add children of start nodeparents[child] = 'start';}
const processed = [];
...
Next, we’ll set the initial value of the node being processed using the lowestCostNode function. Then, we’ll begin a while loop, which will continuously look for the cheapest node.
let node = lowestCostNode(costs, processed);while (node) {
let cost = costs\[node\];
let children = graph\[node\];
for (let n in children) {
let newCost = cost + children\[n\];
if (!costs\[n\]) {
costs\[n\] = newCost;
parents\[n\] = node;
}
if (costs\[n\] > newCost) {
costs\[n\] = newCost;
parents\[n\] = node;
}
}
processed.push(node);
node = lowestCostNode(costs, processed);
}
Here’s a description of what’s happening above in greater detail:
- Get the cost of the current node
- Get all the neighbors (aka “children”) of the current node.
- Loop through each of the children, and calculate the cost to reach that child node. We’ll update the cost of that node in the costs object if it is cheapest or only cost available.
- We’ll also update the parents data structure, so that we can retrace our steps in the end.
- Once the node is fully processed, we’ll push it to our processed data structure.
- Reset the value of the current node to the cheapest, unprocessed node, and repeat.
Finally, once the while loop is complete, we’ll have the lowest cost to reach the finish node. We now want to get the path to that node, which we can do by retracing our steps with the parents object.
let optimalPath = ['finish'];
let parent = parents.finish;
while (parent) {optimalPath.push(parent);parent = parents[parent];}
optimalPath.reverse(); // reverse array to get correct order
const results = {distance: costs.finish,path: optimalPath};
return results;
}; //end of function
Our final result should look like this!
{ distance: 8, path: [ 'start', 'A', 'D', 'finish' ] }
To see the full solution, checkout the gist.
If you are still having trouble, I’d recommend running the code on your machine and changing parts of the program. I’ve found that tweaking and playing around with code really helps me gain a deeper understanding of what is going on.
I hope you enjoyed this explanation. Thank you for taking the time to read this article!
** UPDATE: For more clarity, I revisited my original solution and incorporated feedback and clearer variable names, along with some logging to help understand what is happening. You can find it here.
— — If you enjoyed this piece, please hit the green heart 💚 so others might stumble upon it too! Feel free to follow me on Github or Twitter too.