On this page
When a route planner finds you the shortest way home, it is tackling a problem a Dutch programmer worked out in his head over a cup of coffee in 1956. Edsger Dijkstra's shortest path algorithm is short enough to learn in an evening. This post covers who Dijkstra was, how he came up with the algorithm, a full worked example, the common mistakes and what his way of thinking can teach you.
Who was Edsger Dijkstra?
The ACM Turing Award page for Dijkstra records that he was born on 11 May 1930 in Rotterdam and died on 6 August 2002 in Nuenen, in the Netherlands. He studied physics at Leiden and worked as a programmer at the Mathematical Centre in Amsterdam from 1952 to 1962. When he married in 1957 and gave his profession as programmer, the authorities said no such profession existed, so his marriage certificate lists him as a theoretical physicist.
How did he invent the shortest path algorithm?
In one of his last interviews, published in Communications of the ACM in 2010, Dijkstra explained. In 1956 the Mathematical Centre was opening its new ARMAC computer and needed a demonstration that non-mathematicians could understand. He chose: "What's the shortest way to travel from Rotterdam to Groningen?" He used a simplified road map with 64 cities, "so that in the coding six bits would suffice to identify a city". (Check: 2⁶ = 64.)
He designed the algorithm while shopping in Amsterdam with his fiancée: "tired, we sat down on the café terrace to drink a cup of coffee". He called it "a 20-minute invention" and said it came out simple partly because "I designed it without pencil and paper."
It appeared in 1959 as "A note on two problems in connexion with graphs" in Numerische Mathematik. The same paper gave his method for the shortest network of wire connecting a set of points.
Worked example: finding the shortest route by hand
Here is a small network with sample distances in kilometres (made-up numbers for practice). Roads run both ways.
A to B: 4
A to C: 2
C to B: 1
B to D: 5
C to D: 8
C to E: 10
D to E: 2
Find the shortest route from A to E.
Start. A = 0. B, C, D and E are unknown (infinity).
Settle A (0). Update neighbours: B = 4, C = 2.
Settle C (2), the closest unsettled point. Via C: B = min(4, 2 + 1) = 3; D = 2 + 8 = 10; E = 2 + 10 = 12.
Settle B (3). Via B: D = min(10, 3 + 5) = 8.
Settle D (8). Via D: E = min(12, 8 + 2) = 10.
Settle E (10). Done.
The shortest distance is 10 km along A, C, B, D, E: 2 + 1 + 5 + 2 = 10. Check the alternatives: A, C, E is 12; A, B, D, E is 4 + 5 + 2 = 11; A, C, D, E is 2 + 8 + 2 = 12. All longer.
What mistakes do students make with Dijkstra's algorithm?
Taking the nearest neighbour greedily. From C, the road to E looks direct, but A, C, E costs 12. The algorithm compares totals from the start, not single steps.
Settling a point too early. B first looked like 4, but the route through C gave 3. Only settle the smallest value among all unsettled points.
Forgetting to keep the route. Note which point gave each lowest value (E came from D, D from B, B from C, C from A) so you can trace the path back.
Using negative distances. The method assumes no edge has a negative length; with negative edges a settled value could still improve.
If you are preparing for programming olympiads, our guide to the Indian Computing Olympiad explains the route in.
What else did Dijkstra change?
The ACM page lists much more. With J. A. Zonneveld he wrote the first compiler for ALGOL 60, finished in August 1960. He was probably the first to use a stack for running recursive programs; our post on stacks in Python shows the data structure. His 1968 letter "Go To statement considered harmful" helped start structured programming. He received the 1972 Turing Award "for fundamental contributions to programming as a high, intellectual challenge".
What can a student take from how Dijkstra worked?
Explain it to a non-expert. He picked a problem the audience could understand, and that shaped a clear method.
Remove what is not needed. Working without pencil and paper forced him to avoid complexity.
Check the alternatives. After any answer, test the other routes, as in the example above.
Expect ideas to wait. He published three years later, and its widest use came decades after that.
If you find yourself stuck on the first step of a graph problem, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
Try it now: change the C to B road to 3 km and rerun the algorithm. You should find the shortest route from A to E is 11 km, along A, B, D, E.
