Routing on road graphs
Shortest paths on a planet-sized graph, precomputed enough to answer in milliseconds.
01The intuition
The problem it solves
A road map is a graph: junctions are nodes, road segments are edges, and each edge has a cost, the time to drive it. Finding the fastest route from home to the airport is the shortest-path problem, which Dijkstra's algorithm solves exactly. On a city map with 100,000 junctions it answers in milliseconds.
The planet is different. The road graph of the world has around a billion edges. Dijkstra explores outward from the start in every direction until it reaches the destination, so a 500 km trip touches millions of nodes and takes seconds on one machine. Google Maps answers tens of thousands of route requests a second, each in well under a second, and the travel times change with traffic every few minutes. Running Dijkstra over the whole graph per request is a thousand times too slow.
Build it one piece at a time
Step 1: a small graph, plain Dijkstra. Five junctions, A to E, with drive times in minutes on the edges. From A, Dijkstra keeps a table of the best known time to each node and always expands the closest unsettled node.
| Round | Settled | Best known times |
|---|---|---|
| 0 | A | A 0, B 4, C 2 |
| 1 | C | B 3 (via C), D 7 |
| 2 | B | D 6 (via B), E 9 |
| 3 | D | E 8 (via D) |
The pattern itself is explained in the Dijkstra pattern note. The route home to airport is a path of edges whose costs add up.
Step 2: search from both ends. Run Dijkstra from the start and backwards from the destination at the same time; stop when the two frontiers meet. Each side explores a circle of half the radius, so the work drops by roughly a factor of two to four. Better, but not a thousand.
Step 3: add shortcuts (contraction hierarchies). Offline, once, rank every junction by importance: motorway interchanges high, cul-de-sacs low. Remove the least important node and, if it lay on the only shortest path between two neighbours, add a direct shortcut edge between those neighbours with the combined cost. Repeat for every node. The result is the same graph plus a few hundred million shortcut edges. At query time, search only upward, from each end toward more important nodes, over shortcuts. A cross-country query now touches a few thousand nodes instead of millions and answers in about a millisecond.
Step 4: shard the planet. Split the graph into regions with a few million nodes each, held in memory on separate servers, with the shortcut hierarchy stitched across region borders by a small top-level graph of important nodes. A request first finds the start and end regions, then searches.
Step 5: let costs change. Live traffic changes edge costs every few minutes. The hierarchy is precomputed on free-flow times, and a customisation step re-weights the shortcuts for current traffic in seconds (customisable contraction hierarchies), so routes reflect the jam on the ring road without recomputing the whole structure.
Why it works, with the numbers
Dijkstra's cost grows with the number of nodes it settles. On a flat graph that is proportional to the area explored, roughly the square of the trip distance; the hierarchy makes the search climb to the few important nodes and come back down, so settled nodes grow only with the logarithm of the graph size in practice.
plain Dijkstra, 500 km trip: ≈ 106 to 107 nodes settled, seconds; contraction hierarchy: ≈ 103 nodes, about 1 ms
The guarantee is exactness: with a correctly built hierarchy the route is the true shortest path for the costs used, not an approximation. The costs are honest: preprocessing the planet takes hours of cluster time and must be redone when roads change; the shortcuts add memory; and the live-traffic customisation lags the real world by minutes. Turn restrictions, one-way streets and transit modes are modelled as extra nodes and edges, which multiplies the graph size.
The trade-off you must say out loud
Precomputation buys millisecond queries at the price of a slow rebuild, so road changes and traffic are handled by a fast customisation layer rather than a full rebuild. The interviewer will ask how an ETA accounts for traffic that will exist when you reach the ring road in 40 minutes, which is time-dependent edge costs, and how alternative routes are offered, which is a bounded search for paths within a few percent of the best.
Where it shows up in the 100 Google problems
- Design Google Maps: regional in-memory graphs with contraction hierarchies, traffic customisation every few minutes, and a routing service separate from tile serving.
- Design Uber: the same routing engine estimates pickup times for candidate drivers before a match is made.
- Live traffic from GPS data is the pipeline that produces the edge costs this engine consumes.