Are contraction hierarchies approximate?

The classic correctly constructed method preserves exact shortest-path distances; approximate variants are separate designs.

Can edge weights change?

Yes, but the index needs a suitable update, customization or rebuilding strategy.

Does the method apply only to roads?

It is a graph technique, although its practical efficiency depends strongly on graph structure.

AI Glossary / Graphs and symbolic AI / Advanced

Contraction hierarchies

Definition

Contraction hierarchies are a shortest-path acceleration technique that preprocesses a weighted graph into an ordered hierarchy with shortcut edges. Correctly constructed shortcuts preserve shortest-path distances, allowing later queries to search a restricted part of the augmented graph and reconstruct an exact route.

What it means

Finding one route with a general shortest-path algorithm can be straightforward. Answering many point-to-point queries over a large road network makes repeated exploration expensive. Contraction hierarchies trade preprocessing time and index storage for faster queries.

Vertices receive an order, often described as importance. Less important vertices are contracted first: they are removed from the active preprocessing graph while necessary connections through them are represented by shortcuts. The original route information is retained so a shortcut can later be unpacked.

Importance is an algorithmic ordering choice, not necessarily a road's legal classification or physical size.

The basic technique is exact for the represented graph and edge costs when its construction and query rules are followed. It does not make the underlying travel-time estimates accurate, and it does not automatically remain valid after arbitrary changes to those costs.

How it works

When contracting vertex v, consider paths u→v→w through it between remaining neighbors. Their combined cost is the sum of the two edge costs. A witness search asks whether a route from u to w avoiding v is already available at no greater cost in the current graph.

If such a witness exists, that pair needs no new shortcut. Otherwise, add u→w with the cost of the path through v and retain information needed to recover its constituent edges. Shortcuts can themselves represent paths containing earlier shortcuts.

A query uses a hierarchy-aware bidirectional search. The forward side follows connections towards higher-ranked vertices; the backward side traverses suitable incoming connections towards higher ranks from the destination. Together they can discover an up-then-down representation of an optimal route, with a valid stopping condition.

Finally, recursively unpack shortcuts to obtain the original edge sequence. Returning only a distance and returning a usable route are different workloads.

Changing metrics requires an appropriate update strategy. Customizable contraction hierarchies separate aspects of topology preprocessing from metric customization, while time-dependent variants address additional complications.

Three practical examples

A routing service preprocesses a road graph to serve many distance queries between different origins and destinations.
A logistics analysis tool computes repeated travel costs under a defined metric, then unpacks selected routes for inspection.
A simulation platform compares preprocessing cost, memory and query latency when evaluating graph-routing indexes for a relatively stable map.

Think of it this way

Think of an index that records reliable summaries of local connections so later searches can skip intermediate details and recover them when needed.

The analogy does not mean the shortcut is a new physical road. It represents an existing path, and its usefulness depends on preserving that path's cost and reconstructability. A misleading summary would break the search rather than merely make the explanation less detailed.

Worked example

Deciding whether a shortcut is necessary

Suppose the current directed graph contains A→V with cost 2 and V→B with cost 3. Contracting V would remove the visible A→V→B connection, whose cost is 5.

If the only alternative avoiding V is A→X→B with costs 4 and 4, its total is 8. There is no witness of cost at most 5 in this small graph, so add shortcut A→B with cost 5. Store that it expands through V.

If instead the alternative costs are 2 and 2, its total is 4. That route is a witness: removing V does not require an additional shortcut for this pair, because a route no worse than the one through V remains.

In the first case, a later query using A→B must unpack it to A→V→B. If V→B subsequently changes from cost 3 to cost 10, the old shortcut cost 5 is stale. An update or rebuilding process must restore consistency before the index can support exact claims under the new metric.

Illustrative case study

Fictional case: Alder Routes introduces a preprocessed routing index for repeated warehouse-to-store queries. Initial comparisons with a reference shortest-path routine agree, but a later traffic-cost import updates only the base edges.

A consistency check finds that stored shortcut costs still reflect the old metric. The team versions the graph and index together, adds an appropriate refresh procedure and verifies both distances and unpacked paths after updates.

The lesson is that query speed depends on maintained preprocessing assumptions. A fast answer from an outdated index can be precise about the wrong graph.

Common misconceptions and mistakes

Contracting a vertex permanently deletes its route information. Shortcuts retain enough information for path reconstruction.
Every neighbor pair needs a shortcut. Witness paths can make some shortcuts unnecessary.
A shortcut is a real direct connection. It represents an existing multi-edge path.
Exact routing means exact real-world arrival times. Exactness is relative to the modeled graph and weights.
Faster queries come free. Preprocessing, storage, updates and unpacking all contribute to total cost.

Business use

Contraction hierarchies are attractive when many queries reuse a graph whose structure or metrics can be managed through a defined update process. They are less obviously beneficial for a one-off query where preprocessing dominates.

Evaluate the complete lifecycle: index construction, storage, metric refresh, distance queries and path reconstruction. Keep restrictions such as one-way travel and permitted turns correctly represented. Use reference shortest-path results on sampled and edge-case queries to validate the index after changes, and report performance for the actual workload rather than transferring historical speedups from unrelated networks.

Check your understanding

A path through the vertex being contracted costs 7, and an avoiding witness costs 6. Is a new cost-7 shortcut necessary for that pair?

Answer: No. The witness preserves a route no more expensive than the path through the contracted vertex.

Related terms

Shortest Paths
Dijkstra's algorithm
Bidirectional search
Shortest path
graph preprocessing
witness search
shortcut edge
path unpacking
customizable contraction hierarchies

Learn next

Build the four-vertex example and compare shortest-path distances before and after each contraction choice. Record the original edges behind every shortcut. Then change one base cost and identify which stored summaries would need reconsideration.

Sources

Geisberger, Sanders, Schultes and Delling, original paper, author institution's publication record and linked full text: https://ae.iti.kit.edu/english/999.php

RoutingKit primary implementation documentation: https://github.com/RoutingKit/RoutingKit/blob/master/doc/ContractionHierarchy.md

Customizable Contraction Hierarchies, original research: https://arxiv.org/abs/1402.0402

Original-paper indexed excerpts were reviewed; its linked full-text fetch failed. The shortcut calculation and fictional case are original illustrations.

Previous: Contraction Next: Contractive autoencoder