Dijkstra's algorithm
Also known as: SPF · single-source shortest paths
How a navigator finds the shortest route without trying millions of them: a wave spreads from the start, and each time the nearest unvisited crossing gets its final distance. Invented in twenty minutes on a café terrace in 1956, it still computes routes across the internet.
You are standing on Republic Square and want to walk to the Green Bazaar. A navigator answers in a fraction of a second: 3.8 kilometres. It did not try the routes: with seven thousand crossings there are so many that no amount of time would be enough. It sent a wave through the streets and stopped when the wave reached the bazaar. See for yourself: this is the real Almaty from OpenStreetMap, and the wave is the real Dijkstra's algorithm. Tap the map to move the finish, and press A to move the start.
Watch how the wave grows: not as a circle but along the streets, fast down the long avenues and slowly through blocks where the road winds. The colour shows the distance from the start along the roads. When the wave touches the finish, the route is ready, and it is the shortest one—not a good one, not roughly the best, but the shortest of all possible routes. Why that is guaranteed, we will see below.
The idea
If no road has negative length, the unvisited crossing nearest to the start can no longer get any nearer. Any other way to it goes through a crossing that is farther away, and farther means longer. So its distance can be written down for good and passed on to its neighbours.
The whole algorithm grows out of this one thought. For every crossing we keep the best distance known so far: zero for the start, infinity for the rest. Then we repeat:
- take the unvisited crossing with the smallest known distance and declare its distance final;
- for every street leaving it, check: is it shorter to reach the neighbour through this crossing? If so, write down the new distance.
The second step is called relaxing an edge—a word from old optimisation papers, where an overestimate was “relaxed”. The first step needs the minimum of changing numbers quickly, and there is a ready structure for that: the binary heap.
Step by step
Take a small piece of the same city—the blocks around Republic Square—and go slowly. Every crossing shows its current distance in metres. Blue numbers are final: those crossings have already been taken out of the heap. Orange ones are tentative: a way there is known, but a shorter one may still turn up. Below the map is the heap, smallest first.
Click “step forward” a few times and watch the heap. A crossing reached at the very beginning may wait in it for a long time while nearer places are handled around it. But when it comes to the top, that means every nearer place has been handled already, and nothing shorter will turn up.
Notice one more thing: the same place can enter the heap several times—first with one distance, then, through another street, with a smaller one. We do not look for the old entry to fix it; we simply push a new one. The old one surfaces later and is skipped, because by then the place is already done. This trick is called lazy deletion, and it makes the code simpler at almost no cost in speed.
Why the answer is right
If no edge has negative length, then when a vertex u is taken out of the heap, its recorded distance dist[u] equals the length of the shortest path from the start to u.
Suppose not, and let u be the first vertex taken out with a wrong distance: dist[u] is larger than the shortest path length δ(u). Take some shortest path from the start to u. It begins at a processed vertex (the start is processed first) and ends at the unprocessed u, so somewhere on it there is a first unprocessed vertex y, with a processed vertex x right before it.
When x was processed, its distance was right (u is the first mistake), and the edge (x, y) was relaxed. So dist[y] ≤ δ(x) + w(x, y) = δ(y): a piece of a shortest path is itself shortest. From y to u the same path continues along edges of non-negative length, so δ(y) ≤ δ(u) < dist[u].
We get dist[y] < dist[u], yet the heap gave out u rather than y, so dist[u] ≤ dist[y]. A contradiction.
Read the second paragraph again: non-negative edges are needed in exactly one place—where we said “farther along the path means no shorter”. Remove that, and the proof falls apart. So does the algorithm.
The trap: a negative road
A city has no negative roads, but graphs have them all the time: a discount for a ride, a gain in a currency exchange, the energy an electric car gets back going downhill. Move the slider: the road C → B gets ever “shorter”, and at −3 Dijkstra starts to lie.
What happened: B was taken out of the heap with distance 2 and declared final. Then C was processed (distance 4), and it turned out that B can be reached through C for 4 − 3 = 1. But B is already closed, and the error has travelled on—to D. For graphs with negative edges there is the Bellman–Ford algorithm: slower, but it never jumps to conclusions.
A common mistake is to “fix” Dijkstra by adding the same constant to every edge so that they all become positive. That changes the answer: a path of five edges grows by five constants and a path of two by only two, so a route with few edges wins undeservedly. There is a correct way to rewrite the weights—potentials, as in Johnson's algorithm—but a constant is not it.
Code
The graph is stored as adjacency lists: for every vertex, a list of “neighbour, road length” pairs. The heap is the standard one: heapq in Python and container/heap in Go. Neither has a “decrease key” operation, which is where lazy deletion comes in handy.
The parent array rebuilds the route itself: when a relaxation improves the distance to v, we remember where we came from. From the finish we follow these links back to the start and reverse the list.
Now the same algorithm on the whole city. The graph file lives on the server where the code runs, and the program reads it like any other data. Run both versions and compare the times: Go is several times faster than Python on the same server.
Note the line with break: if you need the route to one finish, there is no point searching further. The wave that reached the bazaar looked at 1422 crossings out of 7909. Without the early exit the algorithm would cover the whole city.
What it costs
Let V be the number of crossings and E the number of streets. Every vertex is processed once, and its edges are looked at then, so O(E) edges are looked at in total. Every successful improvement pushes an entry onto the heap; there are no more entries than edges, and a heap operation costs O(log E) = O(log V). In total:
| How the minimum is found | Time | Best for |
|---|---|---|
| scanning the whole array (as in the 1959 paper) | O(V²) | dense graphs where E is close to V² |
| binary heap | O((V + E) log V) | roads, networks, almost everything in practice |
| Fibonacci heap | O(E + V log V) | the best bound in theory; usually slower than a binary heap in practice |
Road graphs are sparse: in our Almaty E ≈ 1.3 V, and a crossing has fewer than three streets on average. For them the heap wins by a huge margin. Below is a measurement on square grids of different sizes: two implementations, array and heap, on one server. Both axes are logarithmic, so a power law looks like a straight line, and its slope is the power.
The slope of the array version is close to 2: double the city and the time grows fourfold. The heap version grows a little faster than linearly. On a city of a million crossings the difference is seconds against hours.
How navigators manage to be faster
The road graph of a whole country has tens of millions of vertices, and even a good heap does not answer in milliseconds. Go back to the first scene and switch the mode.
- A* adds a hint to the distance—the straight-line distance to the finish—and pulls the wave in the right direction. From Republic Square to the Green Bazaar it looks at 209 crossings instead of 1422. More in the article on A*.
- The two-way search sends two waves, from the start and from the finish, and stops when they meet. Two waves of radius r/2 cover noticeably less than one of radius r: on the same route, 769 crossings. More in bidirectional search.
- Preprocessing. Real navigators rework the graph once, in advance: for example, they build contraction hierarchies, adding “shortcuts over unimportant streets”. After that, a query over a continent's graph takes milliseconds. Inside all these methods is the same Dijkstra, only on a cleverly prepared graph.
Switch to “Fastest” as well: instead of metres the algorithm adds up seconds at assumed speeds—avenues are faster than side streets. The route may get longer in distance and still win in time. The algorithm does not care what it adds up, as long as it is not negative.
Twenty minutes on a terrace
In 1956 Edsger Dijkstra worked at the Mathematical Centre and had to show the public a new computer, the ARMAC. He wanted a problem anyone could understand without any training, and chose the shortest route between cities—on a simplified map of 64 cities, so that a city's number fitted into six bits.
Many years later, in a 2001 interview, he recalled inventing the algorithm in twenty minutes: one morning he was shopping with his fiancée, they got tired and sat down for a coffee on a café terrace. He had no pencil and paper with him, and Dijkstra later counted that as luck: without paper you are almost forced to avoid every complication you can do without. The paper came out only in 1959 and took three pages—“A note on two problems in connexion with graphs”. Its second problem is this algorithm; the first is building a minimum spanning tree.
In the original paper the minimum was found by scanning an array, hence O(V²). Heaps came into the algorithm later, and for sparse graphs that changed everything.
Problems
The first is Dijkstra pure and simple, with the route rebuilt. In the second there are many starts but one wave. In the third you will have to change the graph itself a little: the state “where I am” becomes “where I am and whether I have used the coupon”.
The courier's route Fire stations One free rideData: Almaty roads © OpenStreetMap contributors, ODbL