Dijkstra's Algorithm Was Designed in 20 Minutes at a Café
Zusammenfassung
In 1956, Edsger Dijkstra was sitting with his fiancée at a café terrace in Amsterdam when he designed, entirely in his head, one of the most important algorithms in computer science: the shortest-path algorithm. He had no paper and no pencil. He later said that the absence of writing tools was an advantage — it forced him to keep the design simple enough to hold in his mind. The algorithm was published three years later, in 1959. It is now used billions of times per day in GPS navigation, network routing, and logistics software.
The Problem He Was Solving
Dijkstra was 26 years old and working at the Mathematical Centre in Amsterdam. He was preparing a demonstration for the ARMAC computer and needed a problem that would be interesting to a non-specialist audience.
He chose a routing problem: find the shortest path between two cities in the Netherlands using a simplified road network of 64 cities. He wanted the algorithm to be efficient — not just correct, but fast enough to be demonstrably impressive.
The café session produced the core insight: maintain a set of “visited” nodes with known shortest distances from the source, and at each step, extend the frontier to the unvisited node with the smallest known distance. The structure was elegant and, crucially, simple.
No Paper Required
Dijkstra reflected on this origin story throughout his career. In an interview, he explained: “Without pencil and paper you are almost forced to avoid all avoidable complexities, and to find the real simplifications. I do not know of any algorithm that has been designed in a comparable way.”
The algorithm was not published until 1959 — three years after it was designed. Dijkstra spent that time implementing it and verifying its correctness. The published version, in the journal Numerische Mathematik, remains one of the most-cited papers in computer science.
Ubiquity
Dijkstra’s shortest-path algorithm, or variants of it, is used in:
- Every GPS navigation system (finding the fastest route)
- Internet routing protocols (OSPF, IS-IS)
- Flight booking systems (cheapest connection)
- Supply chain optimization
- Social network analysis (degrees of separation)
The algorithm that emerged from a 20-minute session over coffee in 1956 runs, conservatively, billions of times per day.