How Google Maps Calculates Your Route

Every time you tap "Directions," something happens that you're not allowed to see. An answer arrives in roughly four seconds — confident, specific, quietly authoritative — and you follow it. Hundreds of millions of people do this every day. The system mediating their literal movement through physical space is proprietary, unauditable, and almost completely opaque to the researchers who study it. I find that genuinely strange. Not sinister, necessarily. Just strange in the way that things which work perfectly while remaining invisible tend to be strange.

A new Veritasium video takes a serious run at explaining the mathematics underneath, interviewing researchers including algorithm experts Tim Roughgarden, Jon Kleinberg, Virginia Vassilevska Williams, and Peter Sanders, along with engineer Ben Strasser, who ran benchmarks on the North American road network. What emerges is less a definitive account of what Google Maps does and more an honest reconstruction of what it probably does — which, when you sit with it, is its own kind of interesting.

The problem is worse than you think

Start with scale. The North American road network contains what Veritasium estimates — based on their own modeling, not a primary source I can independently verify — to be over 64 million intersections. (The video doesn't specify whether this includes Canada and Mexico or covers the US alone.) From that network, the number of possible routes between two distant points is, per the video's own simplified estimate using a sparse spatial network model, somewhere around 10^220. That figure comes from Veritasium's calculations, not an external study, so treat it as an order-of-magnitude illustration rather than a citable datum. The underlying point stands regardless: brute-force route-checking is not a computational problem you can solve by throwing faster hardware at it. The math is categorically hostile to that approach.

And yet: four seconds. On your phone. In your pocket.

A man in a café, without pencil or paper

The algorithm at the foundation of all of this was invented in about twenty minutes in 1956 by a Dutch computer scientist named Edsger Dijkstra, while sitting in a café in Amsterdam with his fiancée.

He was trying to solve a practical problem: prove to a skeptical public that computers were useful. (The same public had, delightfully, refused to list "programmer" as a valid profession on his marriage license — his certificate reads "theoretical physicist.") He needed a demo problem that non-mathematicians could understand, with an answer they could verify. He landed on: what's the shortest path between two Dutch cities?

What he came up with, without writing anything down, was an algorithm that explores a graph by always expanding the lowest-cost node first — guaranteeing that when you finally reach your destination, you've found the shortest possible path. "I designed it without pencil and paper," Dijkstra said later. "I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities."

That economy of thought turned out to be the algorithm's superpower. It's been 70 years. Dijkstra's algorithm is still at the core of modern routing systems, layered under optimizations he never imagined but never superseded. Danish computer scientist Mikkel Thorup observed — as quoted in the video — that all theoretical developments in single-source shortest paths had been built on Dijkstra's foundation. That's a remarkable thing to still be true about a twenty-minute café invention.

Why Dijkstra alone isn't enough

The problem is that Dijkstra's algorithm is indiscriminate. Trying to route from Newark Airport to the Central Park Zoo, it expands outward in all directions simultaneously, checking nodes in Staten Island and deep into New Jersey before it closes in on the target. On a city graph, this takes about a tenth of a second — fast, but not fast enough when millions of people are querying simultaneously. On the full North American network, a well-tuned Dijkstra takes around 7 seconds per path on average, per Veritasium's benchmarking. Google Maps needs something closer to a millisecond.

The A* algorithm (A-star) improves on this by adding geographic intuition: it penalizes nodes that are farther from the destination, so the search bends toward the target rather than radiating uniformly. For shortest-distance routing, one of the researchers interviewed in the video — Ben Strasser, who provided the benchmarks — noted that A* explores roughly 9.5 times fewer nodes than Dijkstra on a New York City graph. But for travel time optimization, the math gets ugly fast. The heuristic requires what Strasser described as "a nasty square root computation," and as graphs scale up, A*'s advantage collapses. On travel-time queries, Dijkstra actually pulls ahead.

So A* isn't the answer either. Neither is bidirectional Dijkstra, which runs two searches simultaneously from both endpoints and meets in the middle — cutting the search area roughly in half, but still lacking any sense of road hierarchy. As one researcher in the video put it, these algorithms will still happily check whether driving halfway into an In-N-Out drive-through might somehow be the optimal path. They have no concept of "highway" versus "cul-de-sac."

Shortcuts carved into geography itself

The approach that actually gets close to Google Maps speeds is called customizable contraction hierarchies (CCH). The core idea: pre-process the road network to rank every intersection by importance, then search only upward through that hierarchy from both endpoints.

Importance, in this framework, is mathematically defined rather than manually assigned. The most important nodes are the ones that appear in the most shortest paths — specifically, the nodes that split the graph in half. On the North American network, Veritasium's analysis found (and this is a video-sourced figure, not independently verified) that just 102 nodes split the entire continent's road network in two. Those 102 intersections are the Mississippi River crossings. Bridges over the Mississippi are expensive to build, which means there aren't many of them, which means almost every cross-country route must pass through one. The algorithm independently discovers what geography imposed.

The preprocessing runs in three phases. Phase one — building the node hierarchy and adding "shortcut" edges that encode optimal sub-paths — takes around 1 hour and 40 minutes on the North American network, per Strasser's testing as reported in the video. This phase only needs to rerun when the road network itself changes. Phase two recalculates edge weights when traffic conditions update — Strasser estimated 7 to 8 seconds without parallelization, reducible to about one second with it. Phase three is the actual routing query.

The query results, per Veritasium's reported benchmarks: approximately 200 microseconds per path, exploring an average of 1,450 nodes. Compared to Dijkstra's 7 seconds and 64 million nodes, that's roughly 35,000 times faster, cutting the search space by a factor of around 44,000. A route from San Francisco to Montreal — which Dijkstra would resolve by examining most of the continent — gets handled by checking about 1,236 nodes clustered near the start, the end, and the Mississippi.

What we don't actually know

Here's where I have to be honest about the limits of what any of us can say.

The Veritasium video is explicit about this, and it's the part that lingers with me: we don't know what Google Maps actually uses. The researchers don't know. The academic community working on shortest-path algorithms doesn't know. Contraction hierarchies are the leading candidate — Google's engineering teams have published adjacent research, and the performance characteristics match what we observe — but the specific implementation, the optimizations, the ways it handles real-time traffic integration across millions of simultaneous queries, the decisions made about when to prioritize speed over accuracy, the cases where it might quietly return a route that's good enough rather than optimal — none of that is public.

Think about what that means. There's a system that billions of people use to navigate physical reality. It shapes which roads get traffic, which neighborhoods become accessible, which businesses survive by being on a suggested route and which ones don't. Researchers study it from the outside, reverse-engineering its probable structure from observed behavior and from the academic literature its engineers sometimes publish. The system itself is a black box mediating our movement through the world, and we trust it the way we trust a bridge — completely, without inspection, because it's always held before.

I'm not saying that's wrong. I'm saying it's worth noticing. The next time you tap "Directions" and get an answer in four seconds, you're receiving output from a proprietary system built on a 70-year-old café invention, optimized in ways that are partly understood by researchers who aren't allowed inside, running on a hierarchy derived from the locations of Mississippi River bridges. Dijkstra wanted "simplicity as prerequisite for reliability." What we've built on top of his simplicity is something considerably more complicated — and considerably less visible.

He said he'd settle for haunting programmers who cut corners. I wonder what he'd make of a system too large and too private for anyone to fully audit.

---

— Nadia Marchetti, Unexplained Phenomena Correspondent