I’ve been reading , 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 , so I’d like to share a version of . This algorithm uses a directed, weighted graph to determine the “cheapest” path to reach a node. Grokking Algorithms Python JavaScript Dijkstra’s algorithm 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 and each connection is an Each node can be connected to many other nodes. Graphs can be 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 so that connections run both-ways. node edge. directed undirected Edges in graphs can also be For example, in the graph below, each weight represents the cost it takes to get from point to point. weighted. 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 is connected to nodes and . Node is the “parent” to nodes and and they are the “children” of node A C D A C D, 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 , the first two nodes we have are which has a cost of 5, and which has a cost of 2. is the cheapest node. These are the only nodes we know of so far besides And since we do not yet know the cost for , we’ll set it to Infinity. start A B B finish. finish 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 When a node has many possible parents, we’ll only keep the parent node that leads to the cheapest cost. track of the parent node each node. 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 node yet, since we don’t have the parent of finish 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 , since 5 is cheaper than 8. We add with a value of 9, since the cost to reach is 2, and the cost to reach from is 7, so 7 + 2 = 9. A D B D B We also update our and data structures. We’ll repeat the above steps until we’ve processed all the nodes. processed parents 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 and the nodes, will return the cheapest node that hasn’t been processed. costs 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, , which will take the initial graph as a parameter. We’ll start off by creating the , and data structures. dijkstra costs parents processed 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 function. Then, we’ll begin a loop, which will continuously look for the cheapest node. lowestCostNode while 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 object if it is cheapest or only cost available. costs 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 node. We now want to get the path to that node, which we can do by retracing our steps with the object. finish parents 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.
