Contraction Hierarchies, in depth: shortcuts, witness searches, node ordering and the upward bidirectional query

Contraction and shortcuts

Fix an order of the nodes, called their rank. Contracting a node v means deleting it from the remaining graph. For every pair of remaining neighbours u and w, the path u - v - w might have been the only shortest connection between them. If it was, add a shortcut edge u - w with cost c(u, v) + c(v, w), and remember that its middle node is v. If some other path from u to w avoiding v is no longer, that path is a witness and no shortcut is needed.

After every node has been contracted, put the original edges and all the shortcuts together. This augmented graph has a key property: for any two nodes s and t, some shortest path between them first climbs strictly in rank and then descends strictly in rank. The reason is the shortcut rule. Take any shortest path and look at its lowest-ranked interior node. When that node was contracted, both of its path neighbours were still present, so either a shortcut joining them was added or a witness of equal cost existed. Either way the node can be bypassed without making the path longer, and repeating the argument leaves only an up-then-down path.

Witness searches

A witness search is a local Dijkstra from u in the remaining graph, skipping v, with a cost limit of c(u, v) + c(v, w). If it reaches w within that limit, the shortcut is unnecessary. Exact witness searches would make preprocessing too slow, so implementations cap them, by the number of settled nodes, by hop count, or both.

The cap is safe in one direction only. A search that gives up early and adds a shortcut that was not needed costs memory and query time, but queries stay correct, because the shortcut's cost is a real path cost. A search that wrongly reports a witness would break correctness, and this cannot happen as long as the search only returns true when it actually reaches w within the limit. Tune the cap for preprocessing speed against shortcut count. It never decides whether answers are right.

Choosing the order

Any order produces a correct hierarchy, but a bad order produces a dense graph and slow queries. The order is chosen greedily with a priority that is recomputed as the graph changes. The most important term is the edge difference: the number of shortcuts that contracting v would add minus the number of edges it would remove. Nodes that can be removed without adding shortcuts, such as dead ends and degree-two chain nodes, go first. Implementations add terms that spread contraction evenly across the graph, such as a count of already-contracted neighbours, so that the hierarchy does not grow lopsided.

Recomputing every priority after every contraction is too expensive, so the standard trick is lazy updating. Pop the node with the smallest stored priority, recompute it, and if it is now larger than the next node's stored priority, push it back and try again. Only the popped node's priority is refreshed. Neighbours of a contracted node are the ones whose priorities actually change, and some implementations refresh those eagerly too.

The query

Because some shortest path is up-then-down, a query runs two Dijkstra searches that only relax edges toward higher rank: a forward search from s, and a backward search from t, which on an undirected graph uses the same upward edges. Every node settled by both searches is a candidate meeting point, and the answer is the minimum over candidates of the forward distance plus the backward distance.

Stopping needs care. Unlike plain bidirectional Dijkstra, you cannot stop at the first meeting, because the upward searches do not settle nodes in global distance order. Each side may stop when its smallest queue key is at least the best total found so far. A common optimisation, stall-on-demand, prunes a node when a higher-ranked neighbour proves it was reached suboptimally. The code below omits it for clarity.

A tested implementation

The implementation below is undirected and stores the hierarchy as one upward adjacency map. It was checked against plain Dijkstra on every ordered pair of 40 random graphs with up to 25 nodes, including disconnected pairs, which must return infinity.

import heapq
INF = float("inf")

def witness(g, done, u, target, skip, limit, max_settled=50):
    dist, pq, settled = {u: 0}, [(0, u)], 0
    while pq and settled < max_settled:
        d, v = heapq.heappop(pq)
        if d > limit: return False
        if v == target: return True
        if d > dist[v]: continue
        settled += 1
        for w, c in g[v].items():
            if w == skip or w in done: continue
            if d + c < dist.get(w, INF):
                dist[w] = d + c; heapq.heappush(pq, (d + c, w))
    return False                       # gave up: assume no witness (safe)

def shortcuts(g, done, v):
    nb = [u for u in g[v] if u not in done]
    return [(u, w, g[v][u] + g[v][w])
            for i, u in enumerate(nb) for w in nb[i + 1:]
            if not witness(g, done, u, w, v, g[v][u] + g[v][w])]

def build_ch(adj):
    g = {v: dict(n) for v, n in adj.items()}
    done, rank, gone = set(), {}, dict.fromkeys(g, 0)
    def prio(v):
        live = sum(1 for u in g[v] if u not in done)
        return len(shortcuts(g, done, v)) - live + gone[v]
    pq = [(prio(v), v) for v in g]; heapq.heapify(pq)
    while pq:
        _, v = heapq.heappop(pq)
        if v in done: continue
        p = prio(v)                    # lazy update
        if pq and p > pq[0][0]:
            heapq.heappush(pq, (p, v)); continue
        for u, w, cost in shortcuts(g, done, v):
            if cost < g[u].get(w, INF):
                g[u][w] = g[w][u] = cost
        for u in g[v]:
            if u not in done: gone[u] += 1
        rank[v] = len(rank); done.add(v)
    return {v: {w: c for w, c in g[v].items() if rank[w] > rank[v]} for v in g}

def ch_query(up, s, t):
    dist, pq = [{s: 0}, {t: 0}], [[(0, s)], [(0, t)]]
    best, side = INF, 0
    while pq[0] or pq[1]:
        if not pq[side]: side ^= 1
        d, v = heapq.heappop(pq[side])
        if d > dist[side][v]: side ^= 1; continue
        if d >= best:                  # this side cannot improve the answer
            pq[side] = []; side ^= 1; continue
        if v in dist[side ^ 1]:
            best = min(best, d + dist[side ^ 1][v])
        for w, c in up[v].items():
            if d + c < dist[side].get(w, INF):
                dist[side][w] = d + c; heapq.heappush(pq[side], (d + c, w))
        side ^= 1
    return best

For a directed graph, keep two upward maps: the forward search uses upward out-edges, and the backward search uses upward in-edges, meaning edges x to y with rank(x) above rank(y), traversed in reverse. The witness search and shortcut test then run on directed pairs of an in-neighbour u and an out-neighbour w.

Measured on a grid

I ran the code on a 60 x 60 grid with 3,600 nodes, 6,384 edges (each grid edge kept with probability 0.9) and integer costs from 1 to 10. Preprocessing added 7,973 shortcuts and took 17.1 seconds in pure Python. Over 300 random queries, all answers matched plain Dijkstra.

That is about a 15x reduction on a graph with no real hierarchy: a random grid has no motorways. Road networks, with their strong hierarchy, gain far more. The original paper reported sub-millisecond queries on a continental-scale European road network. The measurement also shows the cost side: on a grid the shortcut count exceeded the original edge count, which is why ordering heuristics matter.

Unpacking shortcuts into routes

A query returns a cost and a meeting node, but users want the route. Record parents in both searches to get the up-down path in the augmented graph, then expand each shortcut. Storing the middle node v with every shortcut makes expansion a simple recursion: shortcut u - w becomes unpack(u, v) followed by unpack(v, w), until only original edges remain. The recursion depth is bounded by the hierarchy's height, and unpacking costs time proportional to the number of original edges in the route. Store the middle node as a 32-bit integer next to the edge, never a list of expanded edges, or memory grows with the square of the path length.

Operational guidance

• Treat preprocessing as a build artefact. Version the hierarchy with the graph snapshot it was built from, and refuse to serve a hierarchy whose snapshot ID does not match the edge data used for unpacking.
• Plan for changing weights. A classic CH must be rebuilt when costs change, because the order and shortcuts depend on them. Customizable Contraction Hierarchies, from Dibbelt, Strasser and Wagner, split the work: a metric-independent order and shortcut structure computed once, then a fast customisation pass that fills in new costs. OSRM, a widely used open-source router, offers both CH and a multi-level partition mode for this reason.
• Model turns explicitly. Turn costs and restrictions are usually handled by building the hierarchy on an edge-based graph, where nodes represent road segments. This multiplies size, so measure memory first.
• Keep a fallback. Plain Dijkstra or A* search on the original graph is the oracle for nightly correctness checks on sampled pairs.

Failure modes

• Overly strict witness limits. They add many unnecessary shortcuts. Answers stay right, but memory and query time balloon. Track the shortcut-to-edge ratio per build.
• Downward relaxation. A query that relaxes all edges, not only upward ones, is still correct but loses the speedup. Assert that the query graph contains only upward edges.
• Stopping at the first meeting. This returns paths that are too long, often by a small amount that goes unnoticed. Use the queue-key stopping rule above.
• Zero-cost and parallel edges. Keep the minimum-cost parallel edge, and make sure witness searches handle zero costs. Never let a shortcut overwrite a cheaper existing edge.
• Stale hierarchies. A closed road still present in the hierarchy produces confident but undrivable routes. Rebuild or customise on every data change, and validate a sample.

Trade-offs

What to do next

1. Run the code above on a small graph and assert that ch_query matches Dijkstra for every ordered pair, including disconnected ones.
2. Log shortcut count, build time and average settled nodes for your graph. Then halve and double the witness limit and compare.
3. Add parent pointers and middle-node unpacking, and test that the unpacked route's cost equals the query cost.
4. Read bidirectional Dijkstra to see how CH's stopping rule differs from the plain version.
5. If your weights change more than daily, prototype customisable CH or an open-source router before writing your own.
6. Review Dijkstra's algorithm in depth and Yen's k shortest paths for the alternative-route features users will ask for next.