Proofs: Contraction hierarchies

Contraction hierarchy queries return shortest paths full

This proof shows: correctness, termination.

Claim. Let all weights be nonnegative and let the hierarchy be built by lines L1 to L5 with any order. For all $s, t$, the query returns $\operatorname{dist}_G(s, t)$, and when it is finite, a walk in $G$ from $s$ to $t$ of that weight.

Setup. Let $\operatorname{rank}(v)$ be the position of $v$ in the order. Let $G_v$ be the remaining graph just before $v$ is contracted: its vertices are those of rank at least $\operatorname{rank}(v)$, and its edges are the original edges among them and the shortcuts added so far, each pair keeping its least weight. Let $H$ be the graph of all edges that are ever stored as upward or downward edges in line L5, with their stored weights. An edge between $a$ and $b$ can only be added or lowered while both are uncontracted, and it is stored, with its final weight, when the first of them is contracted; so each edge of $H$ is stored once, and for $v$ of lower rank than $u$ and $x$, the edges $(u, v)$ and $(v, x)$ of $G_v$ have the same weights in $H$.

Step 1: $H$ has the distances of $G$. By induction on the contractions, every edge of every $G_v$ is an edge of $G$ or a shortcut $(u, x)$ of weight $w(u, v) + w(v, x)$ for edges of an earlier remaining graph, so each edge of $H$ has the weight of a walk in $G$ between its ends. Every edge of $G$ that is not a self-loop is in $G_v$ for the lower end $v$ with at most its weight, so it is in $H$ with at most its weight. Hence $\operatorname{dist}_H = \operatorname{dist}_G$, and expanding an $H$-walk edge by edge (each shortcut through its middle, recursively, which ends since middles have lower rank than both ends) gives a $G$-walk of the same weight.

Step 2: a shortest up-down walk exists. Call an $s$-$t$ walk in $H$ up-down if no inner vertex has lower rank than both its neighbors on the walk; then the ranks rise to a top vertex and then fall. Suppose $\operatorname{dist}(s, t) < \infty$. For a walk $P$ let $c(P) \in \mathbb{N}^n$ count, for each rank $r$, the inner vertices of $P$ of rank $r$, and order these vectors lexicographically starting from rank 0; this order on $\mathbb{N}^n$ is a well-order. Among shortest $s$-$t$ walks in $H$ choose $P$ with the least $c(P)$. If $P$ is not up-down, it has an inner vertex $v$ with neighbors $u, x$ on $P$ of higher rank, edges $(u, v), (v, x)$. Then $u \ne x$, since otherwise $u, v, u$ is a closed walk that can be cut out, giving a shortest walk with smaller $c$. When $v$ was contracted, $u$ and $x$ were in $G_v$ with these edges. By line L3, either $G_v$ without $v$ had a $u$-$x$ walk $W$ of weight at most $w(u, v) + w(v, x)$, all of whose vertices have rank above $\operatorname{rank}(v)$, or line L4 put an edge $(u, x)$ of weight at most $w(u, v) + w(v, x)$ into $G_{v'}$ for the next vertex $v'$, which takes the role of $W$. Each edge of $W$ lies in a later remaining graph, so it is in $H$ with weight at most its weight in $W$. Replacing $u, v, x$ by $W$ gives an $s$-$t$ walk of weight at most $w(P)$, hence shortest, in which one inner occurrence of rank $\operatorname{rank}(v)$ is removed and only inner vertices of higher rank are added. Its count vector is lexicographically smaller, a contradiction. So $P$ is up-down.

Step 3: the two searches compute upward distances. The forward search is Dijkstra's algorithm from $s$ on the upward edges, and the backward search is Dijkstra's algorithm from $t$ on the reversed downward edges, both with nonnegative weights. Let $d^\uparrow(v)$ be the least weight of an $s$-$v$ walk in $H$ whose ranks increase, and $d^\downarrow(v)$ the least weight of a $v$-$t$ walk whose ranks decrease. Every edge of $H$ joins vertices of different rank and is stored as an upward edge out of its lower end or as a downward edge into its lower end, so these are exactly the graphs the two searches use. When a side scans $v$, its label is $d^\uparrow(v)$ (or $d^\downarrow(v)$), by the correctness of Dijkstra; and every tentative label is the weight of a real walk.

Step 4: the query is correct. Every value given to $\mu$ in line L8 is a scanned label plus a tentative or final label of the other side, the weight of an $s$-$t$ walk in $H$, so $\mu \ge \operatorname{dist}(s, t)$ always. If $\operatorname{dist}(s, t) = \infty$, no such walk exists, line L8 never remembers a vertex, and line L9 returns $\infty$. Otherwise let $P$ be a shortest up-down walk (Step 2) with top vertex $z$; its two halves give $d^\uparrow(z) + d^\downarrow(z) \le w(P) = \operatorname{dist}(s, t)$. Suppose the query stops with $\mu > \operatorname{dist}(s, t)$. Then both least keys were at least $\mu > d^\uparrow(z)$ and $> d^\downarrow(z)$, and Dijkstra scans in nondecreasing key order, so both sides had already scanned $z$ with its final labels. At the later of the two scans, line L8 set $\mu \le d^\uparrow(z) + d^\downarrow(z) \le \operatorname{dist}(s, t)$, and $\mu$ never increases, a contradiction. So $\mu = \operatorname{dist}(s, t)$. The remembered vertex $y$ has labels whose walks, read through the predecessors, form an $s$-$t$ walk in $H$ of weight $\mu$ (labels only fall, and the predecessor chain of the last setting has exactly that weight), and by Step 1 its expansion is a walk in $G$ of the same weight.

Termination. The contraction loop handles each vertex once and each witness search is a Dijkstra search on a finite graph. Each query side scans each vertex at most once, the loop stops when both heaps are empty or both least keys reach $\mu$, and the expansion ends by Step 1. $\blacksquare$