Routing and shortest paths at scale

How maps and delivery apps compute routes on graphs with hundreds of millions of edges: Dijkstra and A*, why they are too slow alone, contraction hierarchies and precomputation, live traffic, ETA prediction, partitioning the road graph and map matching.

Reading is half of it. See this used in a real interview: walk through Design Google Maps →

"Get me from here to there" is a graph problem: intersections are nodes, road segments are edges, and travel times are weights. The textbook algorithms are correct but far too slow on a continental road network with hundreds of millions of edges, under thousands of requests per second. Map routing questions test whether you know how precomputation makes it fast and how live traffic keeps it accurate.

The baseline: Dijkstra and A*

• Dijkstra expands nodes in order of distance from the start until it reaches the destination. On a country-sized graph, a long route can explore millions of nodes: seconds per query.
• A\* adds a heuristic (straight-line distance divided by maximum speed) to explore toward the destination first. It helps, but long routes are still slow.
• Bidirectional search runs from both ends and meets in the middle, roughly halving the work.

Fine for a city; not for a production service answering cross-country queries in milliseconds.

Precomputation: contraction hierarchies

The key insight is that long routes use a small set of important roads (motorways, arterials). Contraction hierarchies (CH):

1. Rank nodes by importance.
2. "Contract" unimportant nodes one at a time, adding shortcut edges that preserve shortest distances between their neighbours.
3. At query time, run a bidirectional search that only moves upward in importance from both ends.

Queries touch hundreds of nodes instead of millions, answering in about a millisecond. The cost is a preprocessing step (minutes to hours) and extra memory for shortcuts. Variants like customisable route planning (CRP) separate the slow structural preprocessing from a fast weight update step, which matters for live traffic.

Partitioning the graph

The road graph is split into regions (cells) with relatively few boundary nodes. Distances across each cell between its boundary nodes are precomputed. A long query then works at the cell level and only drills into detail near the start and end. This also lets you shard the routing service by region and update one region's weights independently. See graph data.

Live traffic

Static speed limits give poor ETAs. Real systems:

• Collect GPS pings from phones and vehicles, map-match them onto road segments, and compute current speeds per segment in a stream processor. See batch and stream processing.
• Blend live speeds with historical speeds for that segment, weekday and time of day (traffic at 8 a.m. Monday is predictable).
• Push updated weights to the routing engine every minute or so; CRP-style designs re-customise weights quickly without full preprocessing.
• For long trips, use predicted speeds for the time you will reach each segment, not current ones.

ETA prediction

The shortest path gives a base travel time. A machine-learning model refines it with features (route, time, weather, historical error, turns, traffic lights) and is trained on actual trip durations. Ride-sharing and delivery apps care about ETA accuracy as much as the route itself, because it drives pricing and dispatch. See Design Uber and Design DoorDash.

Map matching

Raw GPS is noisy: points jump between parallel roads and drift in cities. Map matching (often a hidden Markov model over candidate road segments) turns a sequence of points into the most likely path on the road graph. It feeds traffic estimation, trip recording and fare calculation.

Serving

• Routing servers keep the graph and precomputed structures in memory, replicated per region.
• Cache popular origin-destination pairs only briefly, since traffic changes; caching at the level of cell-to-cell distances is more useful.
• Many-to-many queries (one driver to many restaurants, or many drivers to one rider) use matrix algorithms that share work across pairs, which dispatch systems need constantly.
• Return alternatives and recompute on deviation; navigation clients re-route when they leave the path.

In the interview

For Design Google Maps: model the road network as a weighted graph, explain why plain Dijkstra is too slow, introduce precomputation (contraction hierarchies or partition-based) with millisecond queries, add a streaming pipeline turning GPS pings into segment speeds, blend with history, and refine ETAs with a model. Mention sharding by region and many-to-many matrices for dispatch.

Checklist

• Graph model: nodes, directed edges, time-based weights.
• Precomputation (CH or partition-based) for millisecond queries.
• Regions as shards; in-memory graphs.
• Live speeds from map-matched GPS, blended with history and predictions.
• ETA model trained on actual trip times.
• Matrix queries for dispatch, re-routing for navigation.