Finding the Shortest Path in Javascript: Dijkstra’s Algorithm
Find a path between two nodes in a graph such that the sum of the weights of its constituent edges is minimized.
GitHub repo with completed solution code
Note: This is the second post I’ve written on this topic. In the previous post, I implemented a breadth first search to traverse from one node in a binary tree to another. If you aren’t super familiar with navigating node based data structures, want a quick refresh, or want to see an unnecessary amount of slime mold gifs, I recommend checking it out before diving into this solution!
However, the binary tree depth first search I explored in my previous post has a lot of limits. It only works on a very specific type of binary tree structure, which doesn’t make it the best tool for mapping sets of points like actual IRL data stored in a more complex weighted graph.
Therefore, several different algorithms have been developed that modify & expand upon a breadth first search pattern in order to make it functional for mapping the type of graph that can effectively represent real life values and challenges.
So, I’m moving on from a breadth first binary tree search to an algorithm devised by Edsger W. Dijkstra.
Edsger W. Dijkstra was a foundational leader in the development of systems, programming & computing science, and a key figure in the development of structured programming. He lived from 1930 to 2002, and spent much of his life teaching at the university level. Like many other developers of vital algorithms, he was something of a polymath — his early education was in chemistry, then theoretical physics, although he considered going into law. He rather stumbled into working with electronic computers in the early 1950s after an acquaintance offered him a job in the Computation Department of Mathematical Center in Amsterdam. There, he became the first programmer in the Netherlands, despite maintaining a focus in theoretical physics for quite some time.
He pushed to prioritize making programming methods & structures as simple and understandable as possible at all times, something that hadn’t previously been a common concern in the deeply theoretical early programming world. He was greatly influenced by his mathematician mother, saying “she had a great agility in manipulating formulae and a wonderful gift for finding very elegant solutions”.
I wonder if his years spent as a teacher also influenced the importance he placed upon programming code being understandable and usable. Either way, his algorithm was the one that felt most accessible to me, as someone quite new to graph theory.
Dijkstra said of the algorithm:
What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.
So, what are the steps of this algorithm?
- Begin with a set of nodes, all of which are unvisited.
- Create a set of the unvisited nodes called the unvisited set consisting of all the nodes.
- Assign every node an initial distance value. This will be set to zero for the starting node, and infinity for all other nodes.
- Set the starting node as the current node.
- For each current node, calculate the tentative distance to each of its unvisited neighbor nodes. Add the distance from the current node to the neighbor node to the distance from the starting node.
- When all unvisited neighbor nodes of the current node have been mapped, mark the current node as visited, removing it from the unvisited set. Visited nodes will not be checked again.
- If the specific destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance from the start node to the nodes in the unvisited set is infinity (meaning there is no connection between the start node and remaining unvisited nodes), then stop. The algorithm has finished.
- Otherwise, select the unvisited node with the smallest tentative distance, set it as the new “current node”, and repeat the the process of calculating the tentative distance to each of its unvisited neighbor nodes.
If the destination node has the smallest tentative distance among all “unvisited” nodes (and thus could be selected as the next “current”), then the algorithm can stop.
Okay, so where do we start with translating this into JavaScript code?
I’m going to start by creating a JavaScript object called graph populated with key-value pairs. Each key represents a node on the graph. Each value object contains key-value pairs that represent the node’s immediate neighbors and the distance or weight of the path between node & neighbor, i.e. the “edge”.
This gives me a test graph I can navigate.
First, We need to be able to identify the nearest neighboring node. We’ll need to do this repeatedly, so I’ll make this functionality its own separate helper function that we can call as needed.
It’ll take in two arguments — an object comprised of nodes and their distances stored in key — value pairs, and an array list of the visited nodes.
We can iterate through the node keys of the object, and find the node with the shortest distance value. If the node with the shortest distance is in the unvisited set, then that’s the next node we should visit.
Okay, now that we have our workhorse helper method written, we can dive into our larger function that will handle the full graph-navigation process.
Our function will take in three arguments: the graph object we made earlier, the desired start node, and the desired end node.
I’ve pseudocoded out the steps I’d like to take in order to use Dijkstra’s algorithm to work through our graph object and find the shortest path from start node to end node.
That’s a lot of steps! Let’s just start at the beginning.
First, we need a hash object that can keep track of each node’s distance from the start node. As directed by Dijkstra’s algorithm, we’ll start by assigning the tentative distance value “infinity” to the end node. We also want to copy the key-value pairs assigned to the child nodes of whichever node in our graph is our start node into distances.
So, we now have a tracking hash object with a key-value pair with key: endNode and value “infinity” and additional key-value pairs for the startNode’s child nodes.
Great! Now we’ve got a hash object that can keep track of a node’s distance from the start node. We’ll keep tracking this data as we move through the nodes, and return the distance of start node to end node when we finally reach the end node.
Ok, now we need another hash object for keeping track of data we’ll need later — we’ve got one to track our distances, we need another to track paths. When we reach our end node, we want to be able to return not only the distance from the start node, but the path of nodes we took to travel from start node to end node.
We’ll create this path by keeping track of parent-child node relationships. I explored these relationships some in my previous post, so feel free to read that if you want to brush up on these structures.
Since we don’t currently know the end node’s parent node, we’ll assign it a parent value of null. However, we can iterate through all the children of our start node, and assign them a parent value of startNode. That’s enough to get started with tracking parent nodes!
Next, we need to collect a list of visited nodes — I’ll just create an empty array named visited for this purpose.
Now we have a distances object and a visited array, which are the two arguments we needed to pass into the shortestDistanceNode helper function we created earlier. So, now we can take in the distance object which contains the child nodes of our start node, and find out which of them is the nearest to startNode.
Now, we’re going to utilize a while loop to begin processing each node & its children. This loop will run until we’ve visited all the nodes.
For each node, we’ll start by finding the current node’s distance from the start node & its child nodes by looking up the values paired with the keys matching the current node in the graph and distances hash objects.
Now we can iterate through each of those child nodes.
Before we do anything to a child node, we want to make sure it’s not the start node. We don’t want to go in circles, so if a child node is the start node, we’ll skip to the next child node.
Now we’re going to use that distance variable we made for the current parent node a few minutes ago.
We’ll create a new variable called newDistance, and assign it the value of distance + the child’s value — its distance from its parent node. By adding the distance of start node to parent node plus parent node to child node, this will give us the child node’s distance from the start node.
(Unfortunately at this point, my code is a bit too long for my syntax highlighting code snippet generator 😔 so I’m switching to the plain old markup code snippets. I hope that doesn’t impact the readability too badly!)
let findShortestPath = (graph, startNode, endNode) => {
// track distances from the start node using a hash object
let distances = {};
distances[endNode] = "Infinity";
distances = Object.assign(distances, graph[startNode]);// track paths using a hash object
let parents = { endNode: null };
for (let child in graph[startNode]) {
parents[child] = startNode;
}
// collect visited nodes
let visited = [];// find the nearest node
let node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
let distance = distances[node];
let children = graph[node];
// for each of those child nodes:
for (let child in children) {
// make sure each child node is not the start node
if (String(child) === String(startNode)) {
continue;
} else {
// save the distance from the start node to the child node
let newdistance = distance + children[child];// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
// save the distance to the object
// record the path
// move the current node to the visited set// move to the nearest neighbor node
// using the stored paths from start node to end node
// record the shortest path//this is the shortest path// return the shortest path & the end node's distance from the start node
};
If we haven’t already saved this child node in the distances object, recording its distance from the start node, or, if the previously recorded distance is longer than the newDistance value (meaning we just found a shorter path, yay us!) then we assign the newDistance value to the key matching the current child node in the distances hash object.
To keep our record keeping accurate, we also record the parent node of the current child node in the parents object. That way, we can always trace our path back to the start node.
let findShortestPath = (graph, startNode, endNode) => {
// track distances from the start node using a hash object
let distances = {};
distances[endNode] = "Infinity";
distances = Object.assign(distances, graph[startNode]);// track paths using a hash object
let parents = { endNode: null };
for (let child in graph[startNode]) {
parents[child] = startNode;
}
// collect visited nodes
let visited = [];// find the nearest node
let node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
let distance = distances[node];
let children = graph[node];
// for each of those child nodes:
for (let child in children) {
// make sure each child node is not the start node
if (String(child) === String(startNode)) {
continue;
} else {
// save the distance from the start node to the child node
let newdistance = distance + children[child];// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances[child] || distances[child] > newdistance) {
// save the distance to the object
distances[child] = newdistance;
// record the path
parents[child] = node;
}
}
}
// move the current node to the visited set // move to the nearest neighbor node
// using the stored paths from start node to end node
// record the shortest path//this is the shortest path// return the shortest path & the end node's distance from the start node
};
Next, we add the current parent node to the visited array, adding it to the visited set so don’t repeat it as we iterate through future nodes.
Now, we can repeat the process, by using our shortestDistanceNode helper function to find the nearest node, which will re-start the next iteration of our while loop. Our while loop will continue to run, repeating this process, until shortestDistanceNode fails to find a new unvisited node.
let findShortestPath = (graph, startNode, endNode) => {
// track distances from the start node using a hash object
let distances = {};
distances[endNode] = "Infinity";
distances = Object.assign(distances, graph[startNode]);// track paths using a hash object
let parents = { endNode: null };
for (let child in graph[startNode]) {
parents[child] = startNode;
}
// collect visited nodes
let visited = [];// find the nearest node
let node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
let distance = distances[node];
let children = graph[node];
// for each of those child nodes:
for (let child in children) {
// make sure each child node is not the start node
if (String(child) === String(startNode)) {
continue;
} else {
// save the distance from the start node to the child node
let newdistance = distance + children[child];// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances[child] || distances[child] > newdistance) {
// save the distance to the object
distances[child] = newdistance;
// record the path
parents[child] = node;
}
}
}
// move the current node to the visited set
visited.push(node);// move to the nearest neighbor node
node = shortestDistanceNode(distances, visited);
}
// using the stored paths from start node to end node
// record the shortest path//this is the shortest path// return the shortest path & the end node's distance from the start node
};
Okay, so our while loop will run until all the nodes have been visited and mapped. What do we do after that resolves?
We can create an array variable named shortestPath, which initially only contains the the end node. However, we can look up the end node’s parent via its key in the parents hash object, and push it into the shortestPath array. Remember, we recorded parent-child pairs to this object only after finding the shortest distances between nodes & from the start node, so tracing from the end node back to the node we recorded as its parent would be taking one step back along a specific path — the shortest path.
As we stored a record of the shortest distance parent node for each node we visited, we can start a new while loop and find the parent node of each parent node, which ultimately will trace a path back to the start node.
That’s not quite what we want though — we want the shortest path from start to end, not end to start!
Thankfully, JavaScript provides a convenient array.reverse() array method. So, if we reverse our shortestPath array, we’ll end up with an array of nodes which, if iterated through, will yield the shortest path from the start node to the end node.
let findShortestPath = (graph, startNode, endNode) => {
// track distances from the start node using a hash object
let distances = {};
distances[endNode] = “Infinity”;
distances = Object.assign(distances, graph[startNode]); // track paths using a hash object
let parents = { endNode: null };
for (let child in graph[startNode]) {
parents[child] = startNode;
}
// collect visited nodes
let visited = []; // find the nearest node
let node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
let distance = distances[node];
let children = graph[node];
// for each of those child nodes:
for (let child in children) {
// make sure each child node is not the start node
if (String(child) === String(startNode)) {
continue;
} else {
// save the distance from start node to child node
let newdistance = distance + children[child]; // if there’s no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances[child] || distances[child] > newdistance) {
// save the distance to the object
distances[child] = newdistance;
// record the path
parents[child] = node;
}
}
}
// move the current node to the visited set
visited.push(node); // move to the nearest neighbor node
node = shortestDistanceNode(distances, visited);
}
// using the stored paths from start node to end node
// record the shortest path
let shortestPath = [endNode];
let parent = parents[endNode];
while (parent) {
shortestPath.push(parent);
parent = parents[parent];
}
shortestPath.reverse();
//this is the shortest path// return the shortest path & the end node’s distance from the start node
};
We did it! We found the shortest path!
Let’s format the info we’ve collected, so that our function can return it nicely.
We can make one last hash object, this time with who keys: “distance” and “path”.
The value of “distance” will be the actual numeric distance value which is the total distance from the start node to the end node, which is the sum of all the distance values (i.e. edge weights) from the edges between the nodes along the shortest path. We can find this by finding the distance value we saved under the key which matches endNode in the distances hash object.
The value of “path” will be the shortestPath array we just created and populated, which can provide a roadmap of sorts of exactly which nodes to traverse in order to go from the start node to the end node & cover the least distance.
let findShortestPath = (graph, startNode, endNode) => {
// track distances from the start node using a hash object
let distances = {};
distances[endNode] = "Infinity";
distances = Object.assign(distances, graph[startNode]);// track paths using a hash object
let parents = { endNode: null };
for (let child in graph[startNode]) {
parents[child] = startNode;
}
// collect visited nodes
let visited = [];// find the nearest node
let node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
let distance = distances[node];
let children = graph[node];
// for each of those child nodes:
for (let child in children) {
// make sure each child node is not the start node
if (String(child) === String(startNode)) {
continue;
} else {
// save the distance from the start node to the child node
let newdistance = distance + children[child];// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances[child] || distances[child] > newdistance) {
// save the distance to the object
distances[child] = newdistance;
// record the path
parents[child] = node;
}
}
}
// move the current node to the visited set
visited.push(node);// move to the nearest neighbor node
node = shortestDistanceNode(distances, visited);
}
// using the stored paths from start node to end node
// record the shortest path
let shortestPath = [endNode];
let parent = parents[endNode];
while (parent) {
shortestPath.push(parent);
parent = parents[parent];
}
shortestPath.reverse();
//this is the shortest path
let results = {
distance: distances[endNode],
path: shortestPath,
};
// return the shortest path & the end node's distance from the start node
return results;
};
Let’s try a few test rounds in the console to see what this spits out:
Great! 🌟
Our function outputs the shortest path from a given start node to a give end node, and also helpfully provides the total distance value of the weighted edges between nodes.
In the GitHub repo containing the completed solution code, I have included an additional file containing alternate code that logs update messages as it progresses through the algorithm. If visualizing the process is tricky, I recommend running that code and watching the logs progress!
I hope you’re as successful as this corgi in your attempts to find the shortest path between two points!
