Contraction Hierarchies and Preprocessing for Road Networks

A continent-scale road network has tens of millions of vertices, and a Dijkstra run between two cities settles a large fraction of them. No improvement to the queue or the heuristic closes that gap, because the gap is not in the search. It is in the fact that the graph contains far more information than a single query needs. Contraction hierarchies exploit that surplus by spending time before the first query, building an auxiliary graph in which every query settles a small number of vertices.

The contraction operation

Take a vertex $v$ and look at its neighbours in the current graph. Removing $v$ disconnects pairs of neighbours that previously had a route through $v$. If the shortest path between two neighbours $u$ and $w$ passes through $v$, and no alternative route of equal or smaller weight exists, a shortcut edge $u \to w$ of weight $w(u,v) + w(v,w)$ must be inserted to preserve distances. If an alternative route exists and is no more expensive, the shortcut is unnecessary: the pair is witnessed by that route, and the search that establishes this is called a witness search.

Contracting every vertex in some order yields a sequence of graphs. The final structure is not the sequence; it is the union of all original edges and all inserted shortcuts, together with the rank assigned to each vertex, which is its position in the contraction order. A shortcut’s endpoints are both ranked above the contracted vertex, which gives the auxiliary graph a strict upward orientation: every edge can be traversed from lower rank to higher rank.

The witness search is a bounded Dijkstra from $u$ over the neighbourhood of $v$, ignoring vertices ranked below the current level. It is the dominant cost of preprocessing, and its bound, the number of vertices it may settle before giving up and inserting the shortcut anyway, is the central tuning parameter. A generous bound produces fewer shortcuts and a longer build; a tight bound produces more shortcuts and a faster build. Inserting a shortcut that a witness would have made unnecessary is not a correctness error, only a size error, which is what makes the trade safe.

Choosing the order

The order determines everything. Contract vertices in an order that happens to follow a long chain and the shortcuts form a dense mesh; contract in a good order and the shortcut count stays within a small multiple of the original edge count.

The standard priority is the edge difference: the number of shortcuts that contracting $v$ would add, minus the number of edges that would be removed. A vertex with many neighbours and few alternative routes between them has a high edge difference and is contracted late. A degree-two vertex on a long road has edge difference near zero, one edge removed and one shortcut added, and is contracted early.

Edge difference alone is not enough, because it ignores how the contraction affects the remaining graph. Implementations combine it with terms that penalise vertices whose neighbours have already been contracted (a proxy for how much the graph has been distorted), with the number of already-contracted neighbours, and with a term proportional to the vertex’s degree. The combination is a weighted sum whose weights are tuned empirically, and the priority is recomputed lazily: after a contraction, only the neighbours’ priorities can change, and even those are often updated only when the vertex reaches the top of the queue, with the stale value re-evaluated at that point.

The resulting order has a characteristic shape on road networks. Dense clusters such as city centres, where the minor-road graph has high degree, are contracted first, and the long arterial edges survive to the top. The top of the hierarchy is a small set of vertices, sometimes called the core, and it is often only a small percentage of the input. That shape is not imposed; it emerges from the edge-difference priority, and it is the reason the method works on road networks and less well on graphs without geographic structure.

The query

Run a bidirectional Dijkstra as described in Bidirectional Search and the Problem of Knowing When to Stop, with one modification: the forward search relaxes only edges whose head has a higher rank than the current vertex, and the backward search relaxes only edges whose tail has a higher rank than the current vertex in the reversed graph. Both searches therefore move strictly upward in rank and can never descend.

Both searches terminate when their queues are exhausted, not when they meet. The answer is

$$\min_{v} \big( d_f[v] + d_b[v] \big)$$

over all vertices $v$ settled by both searches, and the minimum is taken over the whole run. Stopping early is unnecessary because the upward restriction makes each search’s settled set small: the frontier climbs through the hierarchy and runs out of upward edges quickly.

The reason the restriction preserves correctness is a shortcut-cover argument. Any shortest path in the original graph can be transformed into an up-down path in the hierarchy: walk upward from the source along the contracted sequence, then downward to the target. Each time the original path passes through a contracted vertex, either a shortcut replaces the detour or a witness path does, and the witness is no more expensive. So some up-down path has the same weight as the original shortest path, and the bidirectional upward search finds the cheapest such path. The apex vertex where the two searches meet is the highest-ranked vertex on that path.

Space, and the absence of a worst-case bound

The number of shortcuts is not bounded by a small function of the input size in the worst case. Contraction can produce a graph with $\Theta(|V|^2)$ edges, because a complete bipartite structure with weights arranged adversarially defeats the ordering heuristics. On road networks the observed growth is close to linear, with shortcut counts in the same order as the original edge count and a modest constant, which is why the method is deployed there and not as a general-purpose technique.

The space cost is therefore data-dependent, and any implementation has to decide what to do when the shortcut count exceeds a budget: raise the witness-search bound (fewer shortcuts, slower build), abandon the contraction of the offending vertex and defer it (a worse order), or give up. The practical response is to monitor the shortcut-to-original-edge ratio during construction rather than after it.

Path reconstruction is a further cost. A shortcut edge must remember the two edges it replaced, forming a binary tree per shortcut, so that the original path can be unpacked after the query. A shortcut inserted while contracting vertex $v$ stores $(u,v)$ and $(v,w)$; unpacking recursively yields the original edges. The tree’s total size is proportional to the shortcut count times the average unpacking depth, which on road networks is small but not one.

Variants that reduce the query further

Three extensions are standard.

Customisable contraction hierarchies separate the topology from the weights. The contraction order and the shortcut set are computed once on a metric-independent graph, and each edge carries a vector of metric values; a second phase, the customisation, computes shortcut weights for a specific metric by combining the vectors bottom-up. The customisation is fast enough to be repeated when traffic data changes, which is the reason the technique is used in routing services rather than as a static index.

Hub labelling takes the same idea to its limit: each vertex gets a label listing a set of hubs with distances to them, and a query is an intersection of two sorted label lists. Labels are typically small, tens of entries per vertex on road networks, and the query is a merge rather than a graph search. The construction is related to contraction: the hubs of a vertex are its upward neighbours in the hierarchy, pruned to those that are actually needed.

ALT and other goal-directed heuristics compose with the hierarchy rather than replacing it, though the combination requires care: the heuristic’s potential must be consistent with the reduced graph’s weights, and a potential computed on the original graph is not automatically valid on the shortcut graph. The conditions are those in A* and the Conditions on a Heuristic.

Where preprocessing does not transfer

The method’s advantage comes from the input’s structure. Road networks have small highway dimension, meaning that a small set of vertices lies near every sufficiently long shortest path. Contraction hierarchies exploit that property implicitly, and graphs without it, such as social networks, peer-to-peer overlays, and arbitrary weighted graphs from a database, produce shortcut explosions.

Dynamic graphs break the premise differently. An edge weight change invalidates the shortcuts that depend on it, and the set of such shortcuts can be large. The customisable variant handles weight changes; a topological change, an inserted or deleted edge, requires either a rebuild or a local repair that is not part of the classical method.

The last limitation is the one that matters for choosing between methods. On a graph queried once, the preprocessing cost dominates and plain Dijkstra is better. On a graph queried millions of times with stable topology, the amortised cost is small and the query saving is large. The decision is about the query-to-build ratio, not about the algorithm.