Created in 1956 by Edsger Dijkstra, published in 1959. Single source shortest path problem for non-negative weighted graphs .
Problem
Input: graph with weight function , and a source vertex .
Output: all the shortest paths from where . is defined as the length of shortest path from to , which is just the sum of the weights on the path.
Imagine that the vertices are ping pong balls, and edges are strings that connect them. Intuitively, Dijkstra’s asks us at each step, how much do we have to pull up by ball before the next ball leaves the ground? The ball connected to the shortest rope will lift up first, before all other balls.
Structural lemma
Let such that for each , it is true that . This is the set of nodes that we’ve already found their shortest paths for.
Suppose that such that , it is true that
and we pick the that is the smallest value out of all . Then , and we can immediately bring it into .
Proof
Assume that path is the shortest path . Consider vertex such that , and . We want to show that . There are two cases:
First case
When , meaning we’ve already found the shortest path for the vertex right before .
Then is true, so the inequality above is equivalent to . This is just the definition of the length of , which we’ve already established as a shortest path, and so .
Second case
When . Then, the vertex right before is not in the set , implying that we’ve already crossed over (at least once).
Let be the vertex of where we first crossed over from to . So currently, the path is defined by .
AFC . We know from Characterizations about optimal shortest paths, and we know , because this is just the first case:
- We’ve established to be the shortest path, because of the we derived above. This is the assumption.
- There exists a such that is a path, , and . This has to be true because we defined to be the first vertex that crossed over.
- See the first case for the rest.
The inequality goes
This implies , which means we should have instead chosen vertex to put into our set next instead of . This is a contradiction because we know and we chose instead.
Algorithm
This naturally brings us to an algorithm where at each step, we find this vertex , and add it to our set . We then adjust for all other vertices in . We repeat until every vertex is added to , at which point we have discovered for all .
Procedure
- Initialize a set . Store the current distance in a function . Set and for all other vertices .
- Keep a min-heap of vertices holding , where the keys are .
- Extract the minimum from the heap. has become fixed; set .
- For all such that is an edge, we set for the corresponding vertex in the heap.
Proof of correctness
We maintain two loop invariants. At any point in our algorithm, it must be true that
- if and , then .
Runtime
The algorithm ends when we finish extracting all vertices: there are such operations. The extracted vertex is operated on exactly once, by iterating over its edges, and possibly relaxing their weights. Then, we will decrease the key of each edge at most once, with such operations. We have
Using Fibonacci heaps, we can cut the decrease key operation time down to amortized time, which means runtime decreases to expected .