The Mechanics of Contraction Hierarchies (CH)
Contraction Hierarchies separate routing into two phases: a one-time offline preprocessing phase (taking ~10 minutes for a continent) and an ultra-fast online query phase.
Assign every vertex $v \in V$ a distinct importance rank $\text{rank}(v) \in \{1, 2, \dots, |V|\}$ (residential dead-ends lowest, interstate highway junctions highest). We contract vertices one by one in increasing order of rank:
When contracting vertex $v$, for every pair of remaining higher-rank neighbors $(u, w)$ with $\text{rank}(u) > \text{rank}(v)$ and $\text{rank}(w) > \text{rank}(v)$ such that edges $(u, v)$ and $(v, w)$ exist, we run a local witness search to check if the shortest path $\delta(u, w)$ in the remaining graph is strictly $\le w(u, v) + w(v, w)$ without using $v$. If not (i.e., $u \to v \to w$ is the unique shortest path), we insert a shortcut edge $(u, w)$ of weight $w(u, v) + w(v, w)$.
CH Optimality Theorem: In the shortcut-augmented graph $G^*$, for every pair $(s, t) \in V \times V$, there exists a shortest path of the canonical up-down form:
$$s = u_0 \to u_1 \to \dots \to u_p = m = v_q \to \dots \to v_0 = t$$where ranks strictly increase along the forward prefix ($ ext{rank}(u_0) < dots < ext{rank}(u_p)$) and strictly decrease along the suffix ($ ext{rank}(v_q) > dots > ext{rank}(v_0)$) meeting at the maximum-rank apex vertex $m$!
1. Online Query: Upward-Only Bidirectional Dijkstra
Because every shortest path has an up-down canonical representation in $G^*$, the online query runs two miniature Dijkstras simultaneously:
- Forward Search from $s$ in $G^\uparrow$: Only traverses outgoing edges $(u, x)$ where $\text{rank}(x) > \text{rank}(u)$.
- Backward Search from $t$ in $G^\downarrow$: Only traverses incoming edges $(y, v)$ where $\text{rank}(y) > \text{rank}(v)$.
Because both searches strictly climb the hierarchy toward major highway arterials, the search trees contain only $\approx 200$ vertices each! The true shortest path distance is $\min_{m \in V} (d^\uparrow[m] + d^\downarrow[m])$ over all meeting vertices $m$.
2. Edge-Difference Heuristic & Hub Labeling (2-Hop Cover)
How do we choose the contraction order? Contracting a vertex $v$ deletes $\text{deg}(v)$ incident edges and adds $s(v)$ shortcuts. Ordering vertices by a priority queue of Edge Difference $\Delta(v) = s(v) - \text{deg}(v)$ (plus contracted neighbor depth) keeps the total number of added shortcuts below $0.4 |E|$. Taking this one step further, Hub Labeling (Abraham et al. 2011) stores each vertex's tiny upward search space $L_f(s)$ and $L_b(t)$ as sorted arrays of (hubId, dist), reducing shortest-path queries to a $0.5$-microsecond sorted-array merge intersection!
Compare Dijkstra’s uniform radial frontier against A* directional pruning f(u) = g(u) + h(u) and OSRM Contraction Hierarchies (shortcut insertion w(u,w)=w(u,v)+w(v,w) + upward rank-monotonic bidirectional search).
Invariant & State
To reconstruct the full turn-by-turn geometry of a route without storing path lists on every shortcut, each shortcut edge $e = (u, w)$ stores only a single 32-bit integer: middleVertex = v. Once the optimal meeting apex $m$ is found, a recursive in-order traversal unpacks $(u, w) \to (u, v) + (v, w)$ in $O(|P|)$ time proportional to the number of edges on the final path!
Complexity Matrix (Continental Road Network: ~50M Vertices)
| Routing Algorithm | Preprocessing Time | Visited Nodes / Query | Query Latency |
|---|---|---|---|
| Standard Dijkstra | 0 s | ~25,000,000 | ~3,500 ms |
| Bidirectional A* (Euclidean) | 0 s | ~1,200,000 | ~180 ms |
| Contraction Hierarchies (CH) | ~8 min | ~350 | ~0.3 ms |
| Hub Labeling (HL / 2-Hop) | ~25 min | ~80 hub comparisons | ~0.0005 ms (0.5 µs) |
Production Implementation: CH Upward-Only Bidirectional Query & Shortcut Unpacker
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
struct CHShortcutEdge {
int to;
long long weight;
int middleVertex; // -1 if original road edge, else contracted vertex v
};
class ContractionHierarchyRouter {
public:
ContractionHierarchyRouter(int n, std::vector<int> rankOrder,
std::vector<std::vector<CHShortcutEdge>> upFwd,
std::vector<std::vector<CHShortcutEdge>> upBwd)
: numVertices(n), rank(std::move(rankOrder)),
adjUp(std::move(upFwd)), revUp(std::move(upBwd)) {}
long long queryDistance(int s, int t) const {
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<long long> dF(numVertices, INF), dB(numVertices, INF);
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pqF, pqB;
dF[s] = 0; pqF.emplace(0, s);
dB[t] = 0; pqB.emplace(0, t);
long long best = INF;
while (!pqF.empty() || !pqB.empty()) {
if (!pqF.empty()) {
auto [d, u] = pqF.top(); pqF.pop();
if (d <= dF[u] && d < best) {
best = std::min(best, d + dB[u]);
for (const auto& e : adjUp[u]) {
if (rank[e.to] > rank[u] && d + e.weight < dF[e.to]) {
dF[e.to] = d + e.weight;
pqF.emplace(dF[e.to], e.to);
}
}
}
}
if (!pqB.empty()) {
auto [d, u] = pqB.top(); pqB.pop();
if (d <= dB[u] && d < best) {
best = std::min(best, dF[u] + d);
for (const auto& e : revUp[u]) {
if (rank[e.to] > rank[u] && d + e.weight < dB[e.to]) {
dB[e.to] = d + e.weight;
pqB.emplace(dB[e.to], e.to);
}
}
}
}
}
return best == INF ? -1 : best;
}
private:
int numVertices;
std::vector<int> rank;
std::vector<std::vector<CHShortcutEdge>> adjUp, revUp;
};In both standard Bidirectional Dijkstra and Contraction Hierarchies, the first vertex $v$ reached by both the forward and backward searches is not necessarily the optimal apex $m$! You must maintain an upper bound best = min(best, dF[u] + dB[u]) and continue expanding each queue until its minimum key exceeds best.