Why Google Maps Finds Routes in Milliseconds

Scale of the routing challenge

The North American road system has over 64 million intersections, yielding approximately 10^220 possible routes between two cities. Even checking a billion routes per second would take 10^200 years—yet Google Maps solves this in four seconds.

10^220

possible routes (NY to SF)

Theoretical routes in North American road network

Why speed matters at scale

Millions of users request directions simultaneously. Even if one query takes seven seconds on a single algorithm, the cumulative server load becomes unsustainable. Google needs sub-millisecond query times to handle global demand.

Origin story: Amsterdam, 1956

Edsger Dijkstra invented the shortest-path algorithm during a coffee break with his fiancée while shopping in Amsterdam. He needed a compelling demo to prove the ARMAC computer's power to non-mathematicians. The problem: find the shortest route between two Dutch cities.

Dijkstra's algorithm timeline

How Dijkstra's algorithm works

Starting from a source node, assign it cost zero and all others infinity. Explore neighbors, updating their costs if a shorter path is found. Always explore the unexplored node with lowest cost next. This guarantees the shortest path because all lower-cost paths have already been explored.

Dijkstra's shortest-path algorithm steps

Dijkstra's performance on real networks

On the North American road network, Dijkstra must explore most of the 64 million nodes, taking approximately seven seconds per query. For a trip from Newark Airport to Central Park Zoo, it explored over 65,000 nodes, including irrelevant areas like Staten Island.

7 seconds

Dijkstra query time (North America)

Average runtime for long-distance routing

Why Dijkstra alone isn't enough

Dijkstra searches equally in all directions from the source, exploring nodes regardless of whether they move toward the target. For Google Maps serving millions of simultaneous queries, seven seconds per path is far too slow.

A-star adds geographic intuition

A-star modifies Dijkstra by prioritizing nodes closer to the target. It calculates straight-line distance from each node to the goal and explores nodes with lowest (cost + heuristic distance). This penalizes moves away from the target, making search more human-like.

Nodes explored: A-star vs Dijkstra on NYC route

A-star works better for distance than time

When optimizing for shortest geographic distance, A-star cuts search space by over half compared to Dijkstra. However, when optimizing for travel time (dividing distance by speed limit), A-star's heuristic becomes an extreme underestimate, requiring expensive square-root computations and exploring nearly as many nodes as Dijkstra.

Node exploration: A-star advantage shrinks for travel-time optimization

Searching from both ends

Instead of searching from source to target, run Dijkstra simultaneously from both endpoints. The two search frontiers meet in the middle. Since each frontier expands as a circle of radius R/2 instead of R, total area covered is half, yielding roughly 3x speedup.

Bidirectional search reduces exploration by ~3x

The hierarchy problem

Real road networks have structure: local roads, major roads, highways. Dijkstra and A-star treat all edges equally, so they explore tiny cul-de-sacs with the same priority as interstate highways. Humans naturally meander on local roads, jump to highways, then meander again—but algorithms miss this pattern.

Early GPS approach: manual categorization

1990s in-car GPS systems had surveyors manually annotate roads by speed limit, width, and type, then categorize them into hierarchies (express highway, major road, narrow road). Bidirectional Dijkstra would search narrow roads first, then major roads, then highways. This reduced search area but required manual work and couldn't guarantee shortest paths if candidate areas were miscalibrated.

Nested dissection: automatic hierarchy building

Instead of manual categorization, automatically rank nodes by importance using nested dissection. A node is important if it's part of a small cut that splits the graph roughly in half. For North America, the 102 nodes crossing the Mississippi River are the highest-ranked bottlenecks. Recursively split each region and rank nodes within it, creating a hierarchy without human input.

Nested dissection hierarchy (North America)

Shortcuts: preserving shortest paths

After ranking nodes, add shortcuts between higher-ranked nodes to represent paths through lower-ranked nodes. If a path using only local roads is shorter than the highway route, a shortcut captures it. This ensures the algorithm never misses the true shortest path while still limiting search to high-ranked nodes.

Three-phase execution

Phase 1 (preprocessing): Order nodes and add shortcuts—takes ~100 minutes on North America, runs only when graph changes. Phase 2 (customization): Calculate shortcut weights—takes ~1 second with parallelization, runs whenever traffic updates. Phase 3 (query): Execute bidirectional search on hierarchy—takes ~200 microseconds per query.

Customizable contraction hierarchy workflow

Dramatic performance gains

Customizable contraction hierarchies achieve 35,000x speedup over Dijkstra on the North American network. Query time drops from 7 seconds to 200 microseconds (or as low as 100 microseconds). Average search explores only 1,450 nodes instead of 64 million—a 44,000x reduction in search space.

Query runtime: 35,000x faster with contraction hierarchy

Visual difference: San Francisco to Montreal

A Dijkstra search explores nodes across a massive circular area covering much of North America. The same query on a contraction hierarchy explores only 1,236 nodes, clustered near source and target, with only the critical high-ranked cuts (like the Mississippi) checked in between.

70 years of algorithmic foundation

All modern shortest-path algorithms—A-star, bidirectional search, contraction hierarchies, and recent theoretical breakthroughs—are built on Dijkstra's 1956 algorithm. Danish computer scientist Mikkel Thorup noted that all theoretical developments in single-source shortest paths since then have been based on Dijkstra's work.

Dijkstra's algorithm evolution

Simplicity as strength

Dijkstra's algorithm succeeds because it is elegantly simple. He designed it in 20 minutes without pencil and paper, which forced him to avoid unnecessary complexity. He believed simplicity is a prerequisite for reliability, and that programmers—not machines—are accountable for their work.