In this post, we’re going to discuss an exciting algorithm that is the basis of the modern algorithms that GPS and routing systems use. Originally developed by a Dutch computer scientist, Edsger W. Dijkstra, this algorithm has been improved in many ways throughout the following years. We will be discussing the version that utilizes the min-heap that we discussed previously.
Problem
Suppose we are given a starting point and we’re asked to take the shortest path from that point to another.
Let’s visualize the map like this:
Just for this example, let’s denote the starting point as S and the final as F.
While it may not be apparent to many right now, the shortest path from S to F requires taking the weighted edges 8 and 2 to reach F. We’ll discuss the rationale and approach in the following section but first let’s make a few observations about this graph that will give us insight into the constraints and the appropriate use of this algorithm:
- It has positively weighted edges. While we haven’t seen negatively weighted edges yet, one important key constraint is that Dijkstra’s algorithm only works on positively weighted edges.
- The graph is non-directional. Actually, this doesn’t matter. Dijkstra works for both directed and non-directed graphs. This example uses a non-directed graph. But an important thing to know is that in a non-directed graph, the distance between the starting and final point is the same. This means that if you are asked to start from either one and arrive at the other, the distance will be the same. This is not always true for a directed graph.
Approach
Before we dive into examples and code implementation, let’s first try to get an intuition into how we can break down this problem.
Suppose we have a random graph (different from the one above).
Let’s assume that we know that the shortest path from point A to point B is:
ACDB (read as A → C → D → B)
Regardless of what the graph looks like, we know that the only nodes that will be on the path are A, C, D, and B in that exact order. We’re going to show that we can break this path down into subpaths.
From the path ACDB, we can break this path down as:
ACDB = AC + CDB
AC is the shortest path from A to C. Why? Logically, if AC was not the shortest path from A to C, then there has to be a path that is shorter and this contradicts the very idea that ACDB is in fact the shortest path.
Note: In addition, we are not visiting any other node as we move from A to C because that would contradict the fact that ACDB is the correct path. If there was another node, E, then the path would be AECDB, which is incorrect.
Mathematically speaking:
minimum path < ACDB (if AC is not the shortest path from A to C)
So since AC is the shortest path, we can break down our path further into:
ACDB = ACD + DB (where ACD = AC + CD)
Using the same logic, we deduce that ACD is the shortest path from A to D because AC is the shortest subpath from A to C and CD is the shortest subpath from C to D. And of course, DB is the shortest path from D to B, hence ACDB is the shortest path from A to B. As we continue along with this logic, we see the following idea to be true:
The shortest path, from the starting point to the endpoint, consists of the shortest paths from one node to the next on the path.
What’s great about this idea is that it reveals the essential property of the shortest path and that is that each subpath that we take is minimal.
So, let’s look back at our example from earlier but this time with denoted nodes:
Suppose we’re asked to find the shortest path from A to F. We already mentioned earlier that the solution was ADF, but let’s look at how we can write an algorithm to solve this.
Let’s first give each node a number to represent the distance that has been traveled to reach them. Since our goal is to find the minimum distance, we’ll initialize each node to infinity (∞). However, we’re going to label our starting node, A, with 0 because it takes 0 distance to travel from A to A.
Starting at A, we have to ask ourselves: “What’s currently the shortest path that I can take to get to an adjacent node?” We’re not focusing on getting to F right away. We’re trying to use build subpaths and connect them to each other in order to arrive at our destination.
We’ll start by looking at all of A’s neighbors and update the minimum distance it will take to reach them from A.
So the distance traveled from the origin to the node is determined by:
distance node = min(distance node, distance previous node + edge distance)
In the case of B and D:
distance B = min(distance B, distance A + 5) = min(∞, 0 + 5) = 5
distance D = min(distance D, distance A + 8) = min(∞, 0 + 8) = 8
Here’s an updated visual:
Now, the next logical step is to determine which unvisited node has the shortest path from A. From looking at them in our list, we see that B currently has the smallest distance value, so we traverse to B.
Note: I know that going down B is not the correct path but I want to use this to illustrate how the algorithm will adjust to find the correct one.
From B, we mark B as visited and update the distance of all its unvisited neighbors:
distance C = min(∞, 5 + 2) = 7
distance E = min(∞, 5 + 5) = 10
Note: We’re not updating A again because we’ve already visited it. It’s important to state that:
The distance of a visited node is the shortest distance from the origin to that respective node.
This is because each time we’re done updating the distance of possible paths to traverse from one node to the next, we then take the current shortest path. That path will be the shortest path from the origin to the node.
Then from C, we see that its only neighbor is F so we update the distance of F. But it’s important to note that we haven’t “arrived” at F just yet.
What we’re doing is that we’re scouting for all possible routes to F and determining the shortest distance we can take. This means that we’ll still have to consider other paths.
What’s interesting is that the node with the current shortest path isn’t F (distance 11), but D (distance 8). So, we’re going to now look at D and update its neighbors’ distances:
From D, we update E and F:
distance E = min(10, 8 + 3) = 10
distance F = min(11, 8 + 2) = 10
Since E and F both have the same shortest distance of all the unvisited nodes, our algorithm could either take E or F directly. Nonetheless, we see that the result will be the same regardless of which node is selected:
Code
Before writing the code, let’s do a quick review of the approach that we took above:
- Mark each node as unvisited with a distance of infinity (∞)
- Give our origin node a distance of 0
- Take the node with the shortest distance, mark it as visited, and update the distances of all its adjacent neighbors
- Repeat step 3 until we mark the destination as visited
Now that we have a clear understanding of how our algorithm works, we need to discuss the appropriate data structures to help us implement it.
To keep track of whether a node has been visited and its respective distance, we’ll store them as properties in our node objects.
To visit adjacent nodes, we’ll use the breadth-first search (BFS) method.
In order to retrieve the current minimum distance after each update, we can implement a min-heap to help us get the minimum in O(log n) runtime.
And we’ll utilize the concept of linked lists to keep track of our path.
Code in JavaScript:
Space & Runtime Analysis
Since we’re using a heap and keeping track of whether or not we’ve seen a node, at most, our memory consumption is going to be the number of nodes in the graph. So our spacetime will be:
Space: O(V)
Because we’re using heap operations and looking at every adjacent node, our runtime will be:
Runtime: O(E * log V )
Where V is the number of nodes and E represents the number of edges.
Summary
Congrats! You now know how to find the shortest distance between two nodes on a graph.
However, as graphs get larger and more complex, we’ll need something more advanced to save us time.
While this algorithm is the most basic way to find the shortest path between two nodes, an understanding of it and its methods are foundational to understanding more advanced ones.
