Dijkstra’s Algorithm (and friends)
Have you ever wondered how Google Maps finds you a shortest path from A to B? It may seem a bit magical at first, but this problem, called the single source shortest paths problem, is very well known! In addition, many efficient algorithms have been developed to solve it. Before we proceed further though, let us first clearly answer the question: What is the single source shortest paths problem? Put simply, the single source shortest paths problem is the problem of finding the shortest paths from a source to all other nodes in a graph with weighted edges. One of the most classical algorithms to solve this problem is called Dijkstra’s Algorithm, which can be used when all of our edge weights are nonnegative. However, even if there is a single negative weight, we are forced to use the slower Bellman-Ford algorithm.
Dijkstra’s Algorithm:
Notations:
- 𝛿(s, v) denotes the shortest path distance from s to v, and is left as infinity if v is not reachable from s.
- w(a, b) denotes the weight given to the edge from a to b.
- a → b denotes a path from a to b, could be a single edge.
- v.d references the current calculated shortest distance from s to v.
In simple terms, what Dijkstra’s Algorithm does is to first initialize, like all other civilized shortest paths algorithms, the distances for all but the source nodes to be infinity, and to initialize the source node distance to be 0. Then, it shoves all the nodes in the graph into a min-priority queue, and it iterates until the queue is empty. At each iteration, it pops out a node and relaxes its neighbors that are not in S, meaning that it updates their distances to be min(node.d +w(node, neighbor), neighbor.d). An important implementational detail is that relaxation updates the node’s distance in the priority queue using the decrease_key operation, maintaining the property that the node at the root of the priority queue has the smallest distance (node.d). After all of its neighbors have been relaxed, the node is put into S. Upon termination, all nodes reachable from the source have node.d = 𝛿(s, node) and other nodes have node.d = infinity.
Relaxation can also be modified to build a shortest path tree. To modify relaxation to form a shortest path tree, we only need to modify relaxation to also change the neighbors’ parents to be the current node if the shortest path to the neighbor goes through the current node, and not change it otherwise. In other words, we modify if the current node’s distance plus the edge weight between the node and its neighbor is less than the current known smallest distance to the neighbor.
Dijkstra’s Proof:
It is often common to accept algorithms without proof, for many good reasons. It is simpler, takes less time, and you don’t need to understand the proof to use the algorithm.
However, understanding the proof to the algorithm helps us apply the algorithm to (and admire its beauty on) other problems. It allows us to understand when to use the algorithm. In addition, mathematical/scientific beauty entices readers and provide them with a detailed, yet elevated perspective.
For these reasons, it is in our interest to devote a section to the proof of Dijkstra’s algorithm and examine the mechanics of the algorithm at its core. Let us consider the following proof from CLRS’ famous algorithms textbook.
Theorem: Dijkstra’s algorithm terminates with u.d=𝛿(s, u) for all nodes u in S, the set of completed nodes.
Assume for the sake of contradiction, that there are some nodes that are added to the set S such that node.d != 𝛿(s, node) (They must be this way in order to not have correct shortest distances at the end, as distances are not modified after induction into S). Let the first such node be known as u.
First, it is clear that u cannot be s, the starting node. Why? Because at the time of u’s induction into S, s.d=0, which is equal to 𝛿(s, s), trivially.
Let p be a shortest path from s to u. There must be a point when the path crosses out of S, as s is in S and u is not. Let the two nodes, one in S and the other that isn’t, be called x and y respectively (See Figure).
First let’s list out the facts:
- 𝛿(s, y) ≤ 𝛿(s, u) (y is on the shortest path to u, trivial)
- 𝛿(s, u) ≤ u.d (If there is a path that the algorithm has found through successive relaxation of edges, it must be at least as long as the shortest path)
- u.d ≤ y.d (u was chosen to be inducted into S, not y)
- All together, y.d ≥ u.d ≥ 𝛿(s, u) ≥ 𝛿(s, y).
We know x.d = 𝛿(s, x) when x was inducted into S (u was the first node such that that is not true), and s → x → y is the shortest path from s → y (if there was a shortest path then we would replace it in and get a shorter path). In addition, the edge x → y was relaxed when x was inducted into S, so y.d = 𝛿(s, y). Therefore, u.d=𝛿(s, u), which violates our original assumption, so no nodes can exist with node.d=𝛿(s, node), leading us to conclude that Dijkstra’s Algorithm is correct.
To me, the proof of Dijkstra’s Algorithm is one of the most concise and simple proofs of major algorithms, and it is also one of the most intuitive proofs, as it can be mostly proven with words.
Runtimes:
The runtime of Dijkstra’s can be analyzed piece by piece, which is simpler than it sounds. First, initialization takes O(V) time. Then, the main for loop executes V times, and it must extract the min(with runtime O(log(V))) each time, and then do a decrease_key operation for each edge once. Decrease_key operations take O(log(V)) when the min-priority queue is implemented with a simple binary min-heap, but can be optimized further to O(1) when implemented with a Fibonacci Heap. In total, the runtime of Dijkstra’s Algorithm is O((E+V)log(V)) when implemented with binary min-heaps, and O(E + Vlog(V)) with Fibonacci Heaps. The first one can also be written as O(V²log(V)), and the second as O(V²).
With an understanding of Dijkstra’s in hand, we can now go to view an application in the computer science space that is closely linked to the original algorithm.
Dijkstra’s in Disguise:
Jack goes to Rapture problem (HackerRank).
Jack wants to go from point A to B, through an undirected graph. Interestingly, going from node u to v will cost w(u, v) - total fare so far if w(u, v) > total fare so far, and will cost 0 otherwise.(The problem has been condensed so you don’t have to sort through the background information, though if you are interested, the original problem can be found here.)
To start off, we must notice that the whole deal about edge costs is really just saying this: cost(s, b) = max(cost(s, a), w(a, b)).
The max(previous cost, current edge) operator satisfies a few properties that allow us to use Dijkstra’s Algorithm:
- All paths found by the algorithm are at least as long as the shortest path(trivial).
- If there exists a shortest path from A to B that goes through C, then there exists a shortest path from A to B that consists of the shortest path from A to C, plus the original subpath from C to B. This is true since we could replace the original subpath from A to C with the shortest path from A to C, then get a new path with cost max(𝛿(A, C), cost(original subpath from C to B) ≤ the original max(cost(original subpath from A to C), cost(original subpath from C to B)).
- Adding an edge to a path will only increase the weight of a path, since max(cost(s, a), w(a, b)) ≥ cost(s, a).
To reprove Dijkstra’s for this case, we must have a stronger initial constraint on the path that we build: Let p be a shortest path from s to u with the subpath from s to every node on the path also being a shortest path(Such a path exists using property 2), and let x → y be the first point at which the path exits S, with x in S and y not in S. Then, y.d ≥ u.d ≥ 𝛿(s, u) ≥ 𝛿(s, y). We know that x.d = 𝛿(s, x)(u is the first node chosen to be put into S such that this is not true), and that there exists a shortest path from s to y with a shortest path from s to x, then an edge from x → y. Therefore, the shortest path distance from s to y is max(𝛿(s, x), w(x, y)), and since we relaxed the edge w(x, y) when inducting x into S, y.d is equal to this value. It is hence equal to 𝛿(s, y), and the rest of the proof proceeds as usual.
Inefficiencies and Optimizations
Though it may seem inefficient to calculate the shortest path distances from the source to all nodes when we are only looking for the distance to one node, there(currently, at the time of this writing) exist no algorithms for finding the shortest distance between two nodes that are asymptotically faster than Dijkstra’s Algorithm.
Conclusion
Now that we have gone through the details of Dijkstra’s Algorithm and we have come to admire its uses in another problem, we can take a step back and look at Dijkstra’s Algorithm more generally.
Looking back, any operation that satisfies basic properties like those satisfied by the max(distance, edge) operation is a good fit for Dijkstra’s Algorithm (This includes the * operation if all edge weights ≥1 and + operation) though we must be careful.
We can only apply Dijkstra’s when all edge weights are non-negative. Often, we have to carefully scan through the constraints of the inputs to a problem as well as read between the lines of a real world problem to see what insights from the real world may apply.
The power of Dijkstra’s Algorithm lies not only in its simplicity, but also its efficiency and generalizability. For the problems above, we saw how easy it was to extend Dijkstra’s Algorithm to apply it even in cases in which basic definitions of graphs and distances are modified. Perhaps Dijkstra’s Algorithm can teach us that the (current) best algorithms are not necessarily the most complex and/or specialized.
Dijkstra’s Algorithm is widely regarded as one of the most beautiful algorithms in existence, and it has left and will continue to leave a permanent mark on knowledge and development of algorithms worldwide. The next time you open Google Maps and hit “Navigate”, you’ll have some idea of the magic going on under the hood.
