How he invented Dijkstra’s algorithm
In 1956 the Mathematical Centre needed a public demonstration for its new ARMAC computer that ordinary people could understand.
Dijkstra chose the problem: “What is the shortest way to travel from Rotterdam to Groningen?”
One morning while shopping in Amsterdam with his fiancée Ria Debets (herself a programmer), they sat down on a café terrace for coffee. In about 20 minutes, without pencil or paper, he designed the algorithm entirely in his head. He later said one advantage of working without paper was that it forced him to avoid unnecessary complexity.
He implemented it on a simplified map of 64 Dutch cities (chosen so each city could be encoded in 6 bits). The algorithm was published three years later, in 1959, in a two-page paper titled A Note on Two Problems in Connexion with Graphs.
It remains the foundation of GPS, Google Maps, network routing, and countless other systems.