How Google Maps Finds Your Route, and Why a 66-Year-Old Idea Still Wins
You open Google Maps. You type in an address. You tap Go.
Before you lift your finger from the screen, your route is ready.
That feels obvious now. But think about what just happened. The app considered thousands of intersections, millions of possible road combinations, and dozens of live traffic variables, and it solved the whole thing in less time than a human blink.
The idea behind that calculation was written in 1959 by a Dutch mathematician named Edsger Dijkstra. He sketched it out in about twenty minutes, sitting in a cafe in Amsterdam. He didn't even have a pencil. He worked it out in his head.
In 2025, a team of mathematicians proved, for the first time in sixty-six years, that Dijkstra's approach is not actually the fastest possible. That it has a theoretical speed limit that can be beaten.
Then someone built the faster version and tested it on a real computer. Dijkstra won anyway.
The map as a puzzle
Before we get to the algorithms, we need to see a map the way a computer does.
Every city can be broken into two things: intersections and roads. Mathematicians call them nodes and edges. Your starting point and your destination are nodes. Every street connecting them is an edge, with a number attached representing distance or travel time.
This kind of structure is called a graph. Finding your route is the problem of finding the shortest path through the graph from one node to another.
It sounds simple. But the moment you try to solve it for a real city, the problem explodes. London alone has more than 150,000 intersections. The number of possible routes between two arbitrary points is so astronomically large that checking every single one would take longer than the age of the universe.
We need something smarter.
The world without weights
The simplest version of the problem is easy.
Suppose every road in your city is exactly the same length. One kilometer. Every single one, from a narrow alley to a motorway on-ramp.
In that world, the shortest route is simply the one with the fewest turns. You can find it with something called Breadth-First Search, or BFS. Starting from your origin, you visit every intersection that's one step away, then every intersection two steps away, rippling outward like a wave until you reach your destination.
It works perfectly. It's fast. And it is completely useless in the real world.
A highway exit ramp might be 200 meters. The motorway it feeds onto might be 30 kilometers. BFS treats them identically. It would tell you that two roads one hop apart are the same "distance," regardless of whether one is a hundred times longer than the other.
You need something that understands magnitude, not just hops.
Dijkstra's insight
Dijkstra's solution was almost embarrassingly simple. Instead of rippling outward by number of hops, ripple outward by accumulated distance.
Here's how it works. Start at your origin. Look at everything you can reach directly and note the cost to each. Now pick the single cheapest one: the intersection physically nearest to you. Visit it. From there, look at what it connects to and update your estimates. If you can reach some intersection more cheaply by going through the one you just visited, update the number.
Repeat. Always pick the cheapest unvisited intersection. Never go back. Keep going until you reach your destination.
The key insight: once you've picked a node as the cheapest unvisited option, you've already found the shortest possible path to it. If a shorter path existed, you would have discovered it before now. This means you never need to revisit a node, which is what keeps the algorithm fast.
That's it. Dijkstra's algorithm, complete.
It's provably correct. It always finds the true shortest path. And for six decades it was simply how routing worked. Google Maps uses a version of it. So does Waze, internet packet routing, logistics planning software, and GPS devices.
Use the visualization below to see it in action.
Distances
We start at A with distance 0. Every other node starts at infinity — we know nothing yet.
The sorting problem
Here's the issue that computer scientists spent sixty years staring at.
Dijkstra requires that at every single step, you always pick the cheapest unvisited node. That means you need a constantly updated, perfectly ordered list of candidates: a structure that lets you instantly extract the minimum at any moment.
Maintaining that kind of perfectly ordered list requires sorting. And sorting has a known mathematical cost. For a graph with n intersections and m roads, Dijkstra runs in what's written as O(m + n log n). The "n log n" piece is the sorting penalty.
The question researchers kept asking was: is that penalty actually necessary? Do you really need a perfectly sorted list to find the right answer? Or is there some other way to get to the shortest path without paying the full sorting cost?
For sixty years, nobody could prove either way.
The 2025 breakthrough
In 2025, a team of five researchers from Tsinghua University, Stanford, and the Max Planck Institute published a paper that won the Best Paper Award at STOC, one of the most prestigious theoretical computer science conferences in the world.
Their algorithm is called the Bounded Multi-Source Shortest Path algorithm, BMSSP for short. And it breaks the sorting barrier.
The core idea is this: you don't need to sort everything perfectly. You just need to sort things roughly, most of the time, and precisely only at the very last moment, in very small batches.
Instead of one giant sorted queue of all candidates, BMSSP works in bounded distance bands. It groups nodes into approximate buckets based on how far they might be, runs limited relaxation steps to resolve easy paths without sorting them at all, and only orders nodes precisely when it absolutely has to. The result is a new complexity of O(m log^(2/3) n).
In the mathematics of infinitely large graphs, that's definitively, provably faster than Dijkstra. The sixty-six-year barrier was broken.
The catch
Real computers are not made of mathematics. They're made of silicon.
In late 2025, researchers at the Federal University of Amazonas implemented BMSSP in highly optimized C++ and benchmarked it on physical hardware against actual road networks.
Dijkstra was three to seven times faster.
The culprit is something called cache locality, and it's worth understanding once because it shows up everywhere in computing.
Modern CPUs are extraordinarily fast, but main memory is slow. To bridge the gap, the processor keeps a tiny amount of frequently needed data in a blazing-fast on-chip cache. When your program accesses memory in a predictable, sequential pattern, the CPU can pre-load the next piece before you ask for it. Everything runs at full speed.
The cache miss problem: Every time a program chases a pointer to a random location in memory, the CPU has to stop and wait for slow RAM to deliver it. This pause is called a cache miss and can cost hundreds of processor cycles. Dijkstra almost never causes them. BMSSP causes them constantly.
Dijkstra's data structure is a compact, contiguous heap. Simple, predictable, cache-friendly. The CPU loves it.
BMSSP allocates dynamic recursive frames, maintains multiple hash tables, and chases pointers through memory in patterns the CPU cannot predict. Every pointer chase is a potential cache miss. Those stack up fast.
To even run without crashing on standard hardware, the researchers had to replace some of BMSSP's rigid data structures with hash tables, trading hard mathematical guarantees for statistical ones.
On real hardware
Who actually runs faster?
BMSSP's pointer-chasing and memory overhead make it 3 to 35x slower on real road networks. Dijkstra's compact array structure is a perfect fit for how CPU caches work.
In theory (math land)
Where BMSSP finally wins
Asymptotically, BMSSP wins — but only at 10⁶⁷ nodes. Every graph that has ever existed or ever will exist sits far left of that crossover.
The punchline
The UFAM team wanted to know how large a graph would need to be before BMSSP finally overtakes Dijkstra. They extrapolated from their benchmarks and calculated the crossover point.
The answer: 10 to the power of 67 nodes.
For context: the entire observable universe contains approximately 10 to the power of 80 atoms. A routing graph with 10^67 entries isn't a large city or a continent or the whole Earth. It is a structure so far beyond physical reality that it exists only as an abstraction on paper.
No road network, no internet, no conceivable real-world system will ever get anywhere close.
Why it still matters
You might be thinking: what was the point?
The point is that BMSSP answered a sixty-six-year-old question about the nature of the problem itself. Does finding shortest paths fundamentally require sorting? The answer is no. Routing and sorting are mathematically separable. That's a genuine discovery about information, not just a faster program.
And theoretical results have a habit of becoming practical over time. Hardware changes. Cache architectures evolve. Quantum computing may reshape what "fast" means entirely. A result that's impractical today can be foundational in twenty years.
But right now, in 2026, when you type an address into Google Maps and your route appears before your finger leaves the screen, you're watching a sixty-six-year-old idea run at full speed on silicon.
Dijkstra sketched it out in twenty minutes, without a pencil, in a cafe in Amsterdam. It guides billions of people home every single day. And the most sophisticated mathematical attack on it, from one of the best teams in the field, still can't keep up on a real machine.
That's not a failure of mathematics. That's a tribute to how perfectly one person understood the machine, decades before anyone else thought to ask the question.
If this was worth sharing, send it to someone on 𝕏 or LinkedIn. Got a question or a thought? Drop me a message , I read everything. If this was worth your time, .