How Google Maps Does Not Work

A few weeks ago I watched Veritasium’s video “Google Maps is unreasonably fast. Let me explain” Like most Veritasium content, it was beautifully produced, and it did something valuable: it introduced millions of people to the idea that routing in real navigation apps is far more sophisticated than just running Dijkstra on a road graph.

But even though they mentioned that Dijkstra lived just two hours and one border crossing away from me — which is obviously the real reason I’m writing this — I came away frustrated.

The explanation of Contraction Hierarchies — the algorithmic centerpiece of the video — was vague enough that I couldn’t have implemented anything from it. And while Veritasium was at least honest that Google hasn’t disclosed their actual algorithm, the video still presented CH as the most probable answer. We’ll come back to this question at the end, but for now, there are credible reasons to think it’s something more sophisticated than CH anyway.

So this is my attempt to fix that. If you know what Dijkstra’s algorithm is and roughly how it works, you should be able to finish this article and understand Contraction Hierarchies well enough to implement it. I also have an overview article on pathfinding algorithms if you want to brush up on the fundamentals or explore what else is out there.

Why Dijkstra Doesn’t Scale

Dijkstra is the standard answer to shortest-path problems: priority queue, greedy node selection, neighbor relaxation, repeat. On small graphs it’s fast, but the trouble starts when the graph isn’t small.

OpenStreetMap’s dataset for Europe alone contains roughly 100 million nodes and 120 million edges. When you ask for a route from Brussels to Bucharest, a naive Dijkstra implementation would potentially need to explore tens of millions of nodes before settling on the answer. Even with a modern CPU, that takes minutes — and navigation apps are expected to respond in milliseconds, while simultaneously serving millions of concurrent queries.

A helps somewhat. By adding a heuristic (typically straight-line distance to the destination), A focuses the search and avoids exploring in obviously wrong directions. But on continental-scale graphs, even A* explores far too many nodes to be practical.

The fundamental question that drove a decade of routing research is: can we precompute something about the graph that makes individual queries dramatically (and I mean DRAMATICALLY) cheaper?

The answer is yes. And the most elegant and simple version of that answer is Contraction Hierarchies.

A Brief History

The serious effort to make shortest-path queries fast on road networks began in the early 2000s, largely at the Karlsruhe Institute of Technology (KIT) in Germany. Researchers there — Peter Sanders, Dominik Schultes, and others — developed a series of techniques with names like Highway Hierarchies, Arc Flags, and ALT (A* with Landmarks and Triangle inequality). Each achieved significant speedups but came with tradeoffs: complex preprocessing, large memory footprints, or complicated implementation.

In 2008, a KIT student named Robert Geisberger submitted his diploma thesis titled “Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.” The title is the whole story. Where earlier methods were clever and complicated, CH was clever and simple. The core idea fit on half a page. It achieved query times in the range of microseconds on continental graphs — roughly 1,000x faster than plain Dijkstra — while being straightforward enough that a competent engineer could implement it in a weekend.

The key observation that makes CH work is this: road networks are naturally hierarchical. When you drive from Brussels to Bucharest, the vast majority of your journey happens on highways and major arterials. You leave via local streets, join the highway, stay on it for hours, exit via local streets at the destination. The local streets at both ends are “unimportant” to the long-distance query. If we could somehow encode this hierarchy into the graph ahead of time, queries could skip over the unimportant parts entirely.

The Two-Phase Architecture

Contraction Hierarchies splits routing into two clearly separated phases:

Preprocessing happens once, offline, on the full road graph. It assigns an importance rank to every node and adds shortcut edges to the graph. This takes minutes to hours depending on graph size, but it only needs to be redone when the underlying road network changes significantly.

Query happens at runtime, for each individual routing request. It runs a modified bidirectional Dijkstra on the preprocessed graph and returns in microseconds.

Understanding why these two phases work together is the key to understanding CH. Let’s go through each one.

Phase 1: Building the Hierarchy

What Is Node Contraction?

The preprocessing phase works by contracting nodes one at a time, in order from least important to most important. But before we get into the mechanics, it’s worth asking: why do this at all?

Imagine you’re looking at a road network and you spot a node with exactly two neighbors — say, a point on a straight road segment that exists in the data simply because the road bends slightly there. It sits between node u and node w, and no other roads connect to it. If you replaced that node and its two edges with a single direct edge from u to w — weighted by the sum of both original edges — nothing would change. Every shortest path that used to pass through it still exists, just expressed more compactly. You haven’t lost any route; you’ve just collapsed a redundant middleman into a single edge.

For example, those “redundant” nodes could be contracted.

Now generalise this idea. A node v has not two but several neighbors. You want to remove v and still preserve all shortest-path distances between every pair of those neighbors. So before removing v, you look at every pair (u, w) and ask: is the path *u → v → w* a shortest path between u and w?

If yes, you add a shortcut edge directly from u to w with weight equal to dist(u, v) + dist(v, w). This shortcut absorbs the role v used to play, so future queries can use it without needing v in the graph at all.

If no — meaning there is already another path from u to w that is equally short or shorter, not going through v — then no shortcut is needed. We call such an alternative path a witness: it witnesses the fact that the *u → v → w* path is not the unique shortest path, and therefore v’s removal doesn’t break anything for this pair.

After contracting v, the remaining graph — without v, but with any new shortcuts added — still preserves all shortest-path distances between all remaining nodes. This is the invariant that makes the whole algorithm correct, and it’s what allows you to keep contracting node after node without ever losing the ability to answer shortest-path queries exactly.

Apply this process across the entire graph, contracting nodes from least to most important. What you’re left with is a hierarchy: a layered structure where low-importance nodes have been absorbed into shortcuts, and the top of the hierarchy consists of only the most important nodes — major junctions and highway corridors — connected by edges that implicitly encode all the detail beneath them. This is what makes fast queries possible, but we’ll get to that.

The preprocessing phase works by contracting nodes one at a time, in order from least important to most important.

A Concrete Example

Let’s walk through a tiny example. Consider this graph:

A --2-- B --3-- C
         \     /
          4   1
           \ /
            D

Suppose we decide to contract node D first. D has two neighbors: B and C. We ask: is B → D → C (total weight 5) a shortest path between B and C? The direct edge B-C has weight 3, which is shorter. So there's a witness, and we do not add a shortcut B-C. We simply remove D from the graph.

And it’s worth pausing here on what “contracting D” actually means. D doesn’t vanish from the map — it remains a valid destination. If your query endpoint is D, the algorithm plugs it back into the graph via its original edges to B and C before searching. Contraction only affects how a node participates as an intermediary in the search graph, not whether it’s reachable as a source or destination.

Now suppose we contract node B. B has neighbors A and C (since D is already gone). We ask: is A → B → C (total weight 5) the shortest A-C path? There's no other path from A to C in the remaining graph, so yes — we add a shortcut A-C with weight 5. Then we remove B.

The contracted graph now has nodes A, C, the original A-C shortcut (weight 5), and whatever original edges remain:

A ----5---- C

Any query for the shortest A-C distance will find it directly: 5. If it needs the actual path, it unpacks the shortcut: A → B → C.

The Witness Search

Determining whether a witness exists is itself a shortest-path computation — a local Dijkstra search from u, ignoring v, looking for a path to w no longer than dist(u,v) + dist(v,w). This search can be bounded (we limit the number of hops or the maximum distance it explores) since we only need to know if a short-enough witness exists, not find all paths.

This local search is called the witness search, and it is the inner loop of preprocessing. Its efficiency directly determines how fast preprocessing runs.

Node Ordering: Which Node to Contract First?

The order in which nodes are contracted matters enormously. If we contract high-importance nodes early (like a major highway junction), we’ll generate many shortcuts and the hierarchy won’t be efficient. If we save those for last, the shortcuts added during earlier contractions will be small and local.

The goal is to assign each node an importance score and contract them in ascending order of importance (least important first).

Several heuristics contribute to the importance score:

Edge difference is the most important one. It’s defined as (number of shortcuts added when contracting v) - (number of edges removed when contracting v). If contracting v adds fewer new edges than it removes, the graph gets sparser — that's good. If it adds many more edges than it removes, the graph balloons in size — that's bad, and v should be contracted later.

Contractor depth tracks how many contracted nodes are “below” the current node in the hierarchy. Spreading contraction evenly across the graph avoids creating lopsided hierarchies.

Original edge count — nodes that sit on many original roads (not just shortcuts) tend to be more important and should be contracted later.

In practice, these are combined into a weighted score. The exact weights are tuned empirically, but the edge difference dominates.

One important implementation detail: importance scores are lazily updated. When we’re about to contract the node currently at the top of our priority queue, we recompute its importance score before contracting it. Its neighborhood may have changed since we last computed the score (because other nodes near it have been contracted since then). If its score has increased, we re-insert it into the queue with the new score and pick the next candidate instead. This “lazy update” approach is simpler than maintaining perfectly up-to-date scores for all nodes and produces nearly identical results in practice.

The Result of Preprocessing

Now that you know the nodes and their order were not random during contraction, let’s recap what has happened but now pay attention to those details. We first contracted node D from the graph:

A --2-- B --3-- C
         \     /
          4   1
           \ /
            D

And it became:

A ----2---- B ----3---- C

Then we ran a witness search from A to C, avoiding B. The only remaining path goes... nowhere — D is gone, and there's no other connection. No witness exists. We must add a shortcut.

A ----2---- B ----3---- C
|                       |
+------- 5 (shortcut) --+   ← new shortcut edge, via B

After removing B:

A -----5 [via B]----- C

The shortcut A–C with weight 5 encodes the path A → B → C. Any query for the A–C distance finds it directly. To recover the actual route, it unpacks the shortcut: A → B → C.

After all nodes have been contracted, the result is an augmented graph: the original graph plus all shortcut edges added during contraction. Every node has been assigned a level — its position in the contraction order. Nodes contracted last have the highest level and are the most “important.”

In our running example the contraction order was D → B → A/C, giving these levels:

Level 0      Level 1      Level 2
(least                    (most
important)               important)

    D     →      B     →    A, C

Drawn as a hierarchy, with levels on the vertical axis:

level 2 :  A --------5[via B]-------- C
           |                        / |
level 1 :  +----2---- B ----3------+  1
                      |               |
level 0 :             +----4---- D ---+

Crucially, for any two nodes u and v, there exists a shortest path between them in the augmented graph that is monotonically increasing in node level. That is, there is always a shortest path where you go up in level, reach a peak, then come back down. This is the property that the query phase exploits.

Phase 2: The Query

Given the preprocessed graph with node levels, a query from source s to target t works as follows:

Run two simultaneous Dijkstra searches:

• A forward search from s, but only relaxing [1] edges that go to nodes of higher level than the current node.
• A backward search from t, but only relaxing edges that go to nodes of higher level than the current node (i.e., following edges in reverse, upward).

Footnote 1. When you relax an edge (u, v) with weight w, you check whether the currently known distance to v can be improved by going through u:

if dist[u] + w < dist[v]: dist[v] = dist[u] + w

If yes, you update dist[v] and push v into the priority queue with the new distance. If no, you do nothing.

Both searches explore only “upward” in the hierarchy. They will meet somewhere near the top — at one or more high-level nodes.

As both searches run, we track the best candidate answer: any node m that has been settled [2] by both the forward and backward searches contributes a candidate distance of dist_forward(m) + dist_backward(m). The minimum over all such meeting nodes is the answer.

Footnote 2. In Dijkstra’s algorithm, a node is settled when it is popped from the priority queue — meaning its shortest distance from the source has been definitively found and will not change. From that point on, the algorithm relaxes its neighbors but never revisits the node itself.

Why This Is Correct

The correctness relies on the monotone path property from preprocessing. Any shortest path from s to t can be decomposed into an upward segment from s to some peak node p, and a downward segment from p to t. The forward search will find the upward segment; the backward search (which goes upward from t) will find the reverse of the downward segment. They meet at p, and the sum of their distances is the shortest path length.

One subtlety: you can’t stop either search the moment the searches “meet” (as you might in a naive bidirectional Dijkstra). You need to continue until both searches have settled all nodes with tentative distance less than the current best candidate. The standard bidirectional Dijkstra termination criterion applies here.

Unpacking Shortcuts

The query returns a distance and a path, but the path goes through shortcut edges that don’t correspond to real roads. To recover the actual turn-by-turn route, shortcuts are recursively unpacked.

Each shortcut edge stores a reference to the intermediate node it bypasses. To unpack shortcut A-C (which bypasses B), you replace it with A-B and B-C, then recursively unpack those if they're also shortcuts. This bottoms out when all edges are original road edges.

Unpacking is fast because the recursion depth is bounded by the depth of the hierarchy, which is typically logarithmic in graph size.

Putting it all together

1. Start a forward Dijkstra from s and a backward Dijkstra from t, both restricted to only relaxing edges that go upward in the node ranking.
2. At each step, advance the search whose next node to settle is closer to its origin.
3. When a node v is settled by one search, check whether it has already been reached by the other. If so, compute the path length through v and update the best known distance m if this is an improvement.
4. As soon as the smallest tentative distance (aka the distance of the cheapest unprocessed node in the queue, i.e. the next node that Dijkstra would settle) in both queues exceeds m, stop — any path found from this point on cannot improve the result.
5. Follow predecessor pointers from s and from t toward the node where the two searches met with the shortest combined distance. Wherever a shortcut edge is encountered, replace it recursively with the two original edges it was contracted from, until the full path consists entirely of original graph edges.
6. Return m as the shortest distance and the unpacked sequence of edges as the path.

Why It Is So Fast

The query’s efficiency comes from the restricted search space. Ordinary Dijkstra from s fans out in all directions until it reaches t. CH's upward-only search fans out much more narrowly — it only considers nodes of increasing importance, and the set of important nodes is small.

In practice, on a road network covering a continent, the CH query typically settles a few hundred nodes rather than millions. The bidirectional upward search converges quickly because the number of high-level nodes is small by construction.

Some benchmark numbers from the original Geisberger thesis and subsequent work: plain Dijkstra on a European road network settles ~5 million nodes per query and takes around 5 seconds. CH settles roughly 1,000 nodes and takes under 1 millisecond. That’s a speedup of roughly 5,000x. With careful engineering and SIMD instructions, modern implementations push this into the microsecond range.

Preprocessing takes on the order of minutes for a continental graph and produces a graph roughly 3–5x larger than the original (due to shortcuts). This is a very favorable tradeoff for a system fielding millions of queries per hour.

Common Pitfalls

Incorrect termination condition: The most common bug in bidirectional Dijkstra (CH or otherwise) is terminating too early. Don’t stop when the two frontiers first “meet” — keep going until the termination criterion is properly satisfied.

Directed graphs: Real road networks are directed (one-way streets exist). Your backward search must follow edges in reverse. Make sure your adjacency list supports efficient reverse traversal.

Tied importance scores: When many nodes have the same importance score, the contraction order becomes arbitrary. This is fine for correctness but can affect the quality of the hierarchy. Adding small tie-breaking terms (e.g., node ID) helps reproducibility.

Preprocessing on dynamic graphs: If edge weights change (e.g., due to traffic), the shortcuts may be invalidated. CH with full preprocessing is designed for static graphs. For dynamic weights, look into Customizable Contraction Hierarchies (CCH), which separates the hierarchy construction (topology-only, rarely rerun) from weight customization (fast, run on weight updates).

Memory layout: For query performance, cache-friendly adjacency list layouts (sorted by node level, or by contraction order) make a measurable difference. This matters if you’re squeezing into microsecond territory.

Why Google Probably Uses Something More Sophisticated

The most immediate problem with CH at Google’s scale is that it assumes a static road network. Google Maps, however, deals with real-time traffic, road closures, and constantly shifting travel times — and CH’s preprocessing must be recomputed whenever edge weights change. At Google’s scale, that is prohibitively expensive.

CH is also fundamentally a single-mode, single-metric algorithm. Google routes across walking, cycling, public transit, and driving, sometimes in combination, while also letting users express preferences like avoiding tolls or favouring highways. These customizable weights are a fundamental challenge for CH, since the precomputed hierarchy may no longer be valid once edge weights shift. Techniques like Customizable Contraction Hierarchies (CCH) and Customizable Route Planning (CRP) were specifically invented to address this limitation — and Google has the engineering resources to run something in that family.

Finally, Google’s use cases go well beyond point-to-point queries. Routing for Google Maps Platform, Waze, and logistics customers involves large batches of simultaneous queries and fleet-scale optimization, which suggests infrastructure purpose-built for those demands rather than a general-purpose CH implementation.

What’s Next

The 2015 survey “Route Planning in Transportation Networks” by Bast, Delling, Goldberg et al. is the natural next step if you want to see what came after CH — Hub Labels, Customizable Route Planning, and beyond. And if you build an implementation, I’d love to hear about it.