One morning in 1956, a 26-year-old Dutch programmer named Edsger Dijkstra sat down at a café in Amsterdam with his fiancée. They were tired from shopping. He ordered a coffee and started thinking about a problem.
Twenty minutes later, he had invented one of the most important algorithms in the history of computing — one that now runs inside every GPS system, every internet router, and every app that’s ever told you the fastest route home. He did it entirely in his head, without writing a single thing down.
“It was a twenty-minute invention,” Dijkstra later recalled. “One of the reasons that it is so nice was that I designed it without pencil and paper.”
Who Was Dijkstra?
Edsger Wybe Dijkstra was a Dutch computer scientist who spent most of his career being deeply, almost aggressively, opinionated about how software should be written. He believed programmers should think carefully before touching the keyboard. He wrote most of his professional notes by hand, in fountain pen, in notebooks he distributed to colleagues and filed in an archive he called his EWDs — named after his initials. There are over 1,300 of them.
He was also, famously, skeptical of almost everything. He is often attributed with the sentiment that “computer science” was misleading and that computers are to computing what telescopes are to astronomy. He wrote an essay in 1975 arguing that the BASIC programming language should not be taught to beginning programmers, because it mutilated the mind in ways that made good thinking difficult to recover from.
But in 1956, he was just a young programmer at the Mathematical Centre in Amsterdam, trying to demonstrate what the institute’s new computer could do.
The Problem He Was Solving
The machine Dijkstra was working with was called the ARMAC — a Dutch-built computer that was about to be demonstrated publicly for the first time. Dijkstra wanted to show off its capabilities with a problem the audience could understand and verify: find the shortest route between two cities in the Netherlands.
This is a deceptively simple-sounding problem. You have a map — a collection of cities connected by roads, each road with a known distance. You want to get from Rotterdam to Groningen as efficiently as possible. How do you find the best route?
The naive approach is to try everything: trace every possible path, add up the distances, and pick the shortest. But even for a small map, the number of possible routes explodes very quickly. A map of a dozen cities has thousands of potential paths between any two points. A real road network has millions.
Dijkstra needed something smarter. So he thought about it at the café, and by the time his coffee was gone, he had it.
The Elegant Idea
The key insight behind Dijkstra’s algorithm is this: you don’t need to try every path. You just need to be certain that the path you’ve found so far is the best one available — and then extend it, one step at a time, always toward the nearest place you haven’t visited yet.
Think of it like spreading water across a map.
Imagine you pour a drop of water on your starting city. The water flows outward along every connected road, but it moves more slowly through longer roads — the distance determines the travel time. Whichever city the water reaches first is definitively the closest one, because water always finds the fastest route. There’s no faster path; the water would have taken it already.
Now imagine that city becomes a new source. Water spreads from it too, again moving outward along all connected roads. Whatever city the combined wave reaches next is the second-closest. And so on.
That’s the algorithm. At each step, you mark the nearest-yet-unvisited city as settled — its shortest distance is now confirmed. Then you check all the roads leading out of it, and update your best estimates for where those roads lead. Then you find the next nearest unsettled city, mark it, and repeat.
The process terminates when you’ve settled every city you care about, and you’re left with a guaranteed shortest path from your starting point to anywhere on the map.
Why It Works
The reason this approach produces correct answers — and not just approximately correct ones — comes down to a property of shortest paths that Dijkstra recognized clearly.
If you’ve found the shortest path to a city, then any extension of that path can only get longer. You can never “fix” an already-settled city by discovering a sneaky shortcut that passes through an unsettled one, because the unsettled cities are all farther away than the settled ones. Any path through them starts at a disadvantage.
This is the kind of reasoning that looks obvious after someone explains it, and isn’t at all obvious before. Dijkstra saw it clearly enough to work it out in his head while his fiancée rested. The algorithm is a product of that clarity: no wasted steps, no backtracking, no trying anything twice.
The Three-Year Paper
Dijkstra had the idea in 1956. The paper describing it — a short, elegant note called “A Note on Two Problems in Connexion with Graphs” — wasn’t published until 1959.
“It was published in ’59,” he said in a later interview, “three years late.”
Part of the delay was practical: the algorithm solved its intended problem (the ARMAC demonstration went well), and Dijkstra moved on to other things. Part of it was the state of the field — computer science journals in the late 1950s were still figuring out what kind of work they were meant to publish. A theoretical result about graph traversal wasn’t obviously more important than anything else.
The paper, when it finally appeared in the journal Numerische Mathematik, was barely three pages long. It is now one of the most cited computer science papers ever written.
Where It Lives Today
The most visible use of Dijkstra’s algorithm is navigation. When Google Maps or Apple Maps calculates the fastest route from your house to the airport, it’s solving the same problem Dijkstra solved for the Dutch road network in 1956 — just with more nodes, more edges, and live traffic data feeding into the edge weights. The core logic is unchanged.
But routing apps are only the beginning. Every time you send an email, the routers that pass your message across the internet are solving a version of Dijkstra’s shortest path problem — choosing the most efficient route through the network of interconnected machines. The OSPF protocol, which has been a backbone of internet routing since the 1980s, is built directly on the algorithm.
It shows up in biology (modeling protein folding), in chip design (routing wires on a circuit board), in games (pathfinding for AI characters navigating a level), and in logistics (optimizing delivery routes). Anywhere a problem can be expressed as “find the cheapest way to get from here to there,” Dijkstra’s twenty minutes are at work.
The Connection to Today
If you’ve ever written a pathfinding routine — in a game, in a network analysis script, even as an interview problem — you’ve encountered this algorithm’s descendants. The A* algorithm that’s ubiquitous in game development is a direct extension of Dijkstra’s approach, adding a heuristic guess about which direction to explore first to make it faster in practice.
Understanding Dijkstra’s original algorithm makes A and its cousins click into place. The structure is the same: settle the nearest node, extend outward, repeat. A just adds a thumb on the scale to explore more promising directions first.
What’s remarkable, looking back, is how much Dijkstra got right while sitting at a café table in Amsterdam with nothing but his own mind. The algorithm has been refined, optimized, and extended in a hundred directions over the past seven decades. But the core idea — spread outward from the source, always settling the nearest unsettled node — hasn’t needed changing. It was right the first time.
A Curiosity to Pursue
Dijkstra’s original paper is still available and worth reading — it’s short enough to finish with a second cup of coffee. Look for “A Note on Two Problems in Connexion with Graphs” by E.W. Dijkstra, Numerische Mathematik, 1959.
Or try this: pull up any mapping app and ask it for the fastest route between two distant cities. Then ask it for the shortest route by distance. The two answers will often diverge — which raises the question of how the algorithm weights its edges. Traffic, road type, speed limits: each one becomes a number, and Dijkstra’s logic takes it from there.
The twenty-minute idea is still running, billions of times a day.
