You type two addresses into a navigation app. Within a fraction of a second, it returns a route. Not an approximate one. The shortest one, accounting for real road constraints, distances, and travel times.
The road network it searched could span an entire continent. The graph underlying Europe's road network alone has hundreds of millions of nodes and edges. So how does the system search it so quickly?
The answer isn't one clever algorithm. It's a progression of improvements, each one shifting more work from query time to preprocessing, until the actual online search becomes almost trivially small.
The Graph Underneath
A road network maps naturally onto a weighted directed graph. Intersections become nodes. Roads become edges. Travel time or distance becomes the edge weight. Finding the fastest route between two places becomes finding the minimum-cost path between two nodes.
The challenge is that this graph is enormous, and the number of possible paths through it grows fast. Brute force, trying every possible route to find the best one, is completely impractical. The problem isn't finding a route. It's finding the optimal route without exploring most of the graph.
Dijkstra's Algorithm
The first serious solution is Dijkstra's algorithm. It works with non-negative edge weights, which road networks satisfy, and it's guaranteed to find the optimal path.
The mechanics are straightforward. Dijkstra maintains the best-known distance to every node, initially infinity for all except the source, which starts at zero. At each step, it selects the unvisited node with the lowest current distance, then relaxes its outgoing edges: for each neighbor, if the path through the current node is cheaper than what we've recorded, we update the neighbor's distance. A priority queue makes selecting the cheapest unvisited node efficient.
Source: A, Destination: F
Initial distances: A=0, B=∞, C=∞, D=∞, E=∞, F=∞
Step 1: Visit A, relax neighbors → B=4, C=2
Step 2: Visit C (cheapest), relax neighbors → D=5, E=8
Step 3: Visit B, relax neighbors → D=4 (updated)
...until F is settled
The problem is that Dijkstra expands outward from the source in all directions simultaneously. To find the route from London to Edinburgh, it might settle nodes across most of England before reaching Edinburgh. For queries spanning a large area, the search region grows enormous.
A* Guides the Search
A* improves on Dijkstra by adding a heuristic that estimates how promising each node is relative to the destination.
f(n) = g(n) + h(n)
Where g(n) is the cost from the source to node n, and h(n) is an estimate of the remaining cost from n to the destination. A* prioritizes nodes with lower f(n) values, guiding the search toward the destination rather than expanding uniformly.
For road networks, straight-line geographic distance is an intuitive heuristic: a node geographically closer to the destination is plausibly a better candidate to explore next. For the heuristic to guarantee an optimal solution, it must be admissible: it must never overestimate the true remaining cost. Straight-line distance works because real roads are never shorter than straight lines.
A* can dramatically reduce the number of nodes visited compared to Dijkstra. But it still operates on the entire road graph and can be slow for long-distance queries where the heuristic doesn't guide the search effectively.
Bidirectional Search
Another improvement is running two simultaneous searches: one forward from the source, one backward from the destination. Both searches expand inward, and they meet somewhere in the middle.
Source ──────────→ meeting region ←────────── Destination
This reduces the search region compared to a single-direction Dijkstra, though the savings depend on graph structure and the query. The technical details of when the bidirectional searches are terminated and how the optimal meeting point is identified require care to get right.
Bidirectional search is useful, but it still operates on the unmodified graph. Which brings us to the more fundamental question:
What if we could do most of the expensive work before the user ever asks for directions?
Contraction Hierarchies
Contraction Hierarchies are built on a different insight. Instead of making each query search faster on the same graph, preprocess the graph so that future queries search a much smaller, smarter structure.
The first step is assigning an importance ordering to nodes. Some intersections are genuinely more important for long-distance travel than others. A residential dead-end street is barely relevant. A major motorway junction might sit on the optimal path for millions of routes. The exact ranking uses metrics like edge difference: how many shortcut edges would need to be added if this node were removed.
Once nodes are ranked, the algorithm contracts them in order from least to most important.
When a node B is contracted, it's temporarily removed from the graph. If the shortest path between any pair of B's neighbors went through B, and no alternative path of equal or lesser cost exists, a shortcut edge is added directly connecting those neighbors:
Before contracting B:
A ──(3)──→ B ──(2)──→ C
After contracting B:
A ──────────(5)──────→ C (shortcut)
Crucially, before adding each shortcut, the algorithm runs a witness search: a limited Dijkstra that checks whether another path already connects those neighbors with the same or lower cost. If such a path exists, the shortcut isn't needed. This keeps the graph from bloating with redundant shortcuts.
The important point: contracting a node doesn't delete information. It replaces multi-hop paths through unimportant nodes with direct shortcut edges, preserving all relevant shortest-path distances.
After all contractions, the graph has an upward structure. Every edge points from a less important node to a more important one.
Why This Changes the Query
Preprocessing transforms the problem. During a query:
- A bidirectional search runs on the contracted graph.
- The forward search from the source follows only upward edges, moving toward increasingly important nodes.
- The backward search from the destination does the same.
- Both searches climb the hierarchy and meet near the top.
Local streets
↓
Minor intersections
↓
Major junctions
↓
Regional highways
↓
Major motorways
The forward and backward searches climb this hierarchy, meet near the top, and the optimal path is reconstructed by unpacking the shortcuts.
The search doesn't have to explore local streets across the entire graph. It quickly ascends to important nodes and meets the backward search. Instead of settling millions of nodes, the query might settle thousands.
This is the key insight: Contraction Hierarchies don't make Dijkstra magically faster. They change the graph that the query has to search.
Preprocessing vs Query Time
The two costs are fundamentally different:
Preprocessing (offline, done once):
- Rank nodes by importance
- Contract nodes in order
- Run witness searches
- Add shortcut edges
- Build the hierarchical graph structure Query (online, runs millions of times):
- Receive source and destination
- Run bidirectional hierarchical search
- Unpack shortcuts to reconstruct the route Preprocessing is expensive. It might take minutes for a continental road network. But it happens once. The millions of queries that follow operate on a structure designed to make them cheap.
This is a general engineering principle that goes beyond routing: the fastest online computation is often the computation you moved offline.
Some routing systems extend this further with Customizable Contraction Hierarchies (CCH), which separate the topology-dependent preprocessing from the weight-dependent parts. Road topology changes slowly, but edge weights change constantly due to traffic and road conditions. CCH allows the metric-sensitive parts of preprocessing to be updated quickly without rerunning the full contraction.
Modern road-routing systems use techniques such as Contraction Hierarchies and related hierarchical routing methods. The exact approach used in production systems like Google Maps or Apple Maps isn't publicly documented in full detail, but hierarchical preprocessing is well-established in the academic literature and widely used in practice.
The progression from brute force to Contraction Hierarchies isn't a series of marginal improvements. Each step changes what the algorithm is actually doing:
Brute force → try everything
Dijkstra → search optimally but expands too far
A* → guide the search toward the destination
Bidirectional → search from both ends
Contraction Hierarchies → preprocess the graph so queries barely have to search it
The impressive part isn't any single algorithm. It's the realization that you can invest heavily in offline work to make the online problem almost trivially small. A query that once required exploring millions of nodes can be answered by exploring thousands, because the expensive structural work already happened before you ever asked the question.
Top comments (0)