Proofs: Eppstein's k shortest paths

Eppstein's algorithm lists the k lightest walks full

This proof shows: correctness, termination.

Claim. Let $G$ have real weights, and let $s, t$ be vertices and $k \ge 0$. If a negative cycle lies on some $s$-$t$ walk, EPPSTEIN reports it. Otherwise it ends and outputs $\min(k, N)$ different $s$-$t$ walks, where $N \le \infty$ is the number of $s$-$t$ walks, in nondecreasing order of weight, each with its correct weight, such that every $s$-$t$ walk not output weighs at least as much as the last walk output.

Walks are sequences of edges, so parallel edges give different walks.

Step 1: the restriction. Let $R$ be the set of vertices that are reachable from $s$ and reach $t$. Every vertex of an $s$-$t$ walk is in $R$, since the prefix of the walk reaches it from $s$ and the suffix leads from it to $t$. So the $s$-$t$ walks of $G$ and of $G[R]$ are the same. Conversely, every cycle $C$ in $G[R]$ lies on an $s$-$t$ walk: go from $s$ to a vertex of $C$, around $C$, and on to $t$. So $G[R]$ has a negative cycle exactly when a negative cycle lies on an $s$-$t$ walk. Dijkstra's algorithm (when all weights in $G[R]$ are nonnegative, so no negative cycle exists) or Bellman-Ford on the reversed graph finds the distances $d(v)$ from each $v \in R$ to $t$ or reports a negative cycle of $G[R]$, and the report is correct by the correctness of those algorithms. If $t$ is not reachable from $s$, then $s \notin R$, there is no $s$-$t$ walk, and the empty output is correct. From now on assume $s \in R$ and no negative cycle in $G[R]$; then $d(v)$ is finite for all $v \in R$.

Step 2: the tree. For $v \in R \setminus \{t\}$, let $\mathrm{next}(v)$ be the vertex that last lowered $d(v)$, and the tree edge the edge used. At the end, $d(v) = w(v, \mathrm{next}(v)) + d(\mathrm{next}(v))$, and the tree edges form a tree into $t$: a cycle among them would be created by a strict decrease of a label along it, which forces a negative cycle (the standard predecessor-graph argument for relaxation algorithms). So from every $v \in R$, following tree edges reaches $t$ after finitely many steps; write $P(v)$ for this tree path, and note $w(P(v)) = d(v)$. Here $P(t)$ is empty.

Step 3: sidetracks. Every edge $e = (u, x)$ of $G[R]$ that is not a tree edge is a sidetrack, with $\delta(e) = w(u, x) + d(x) - d(u)$. Since $d(u) \le w(u, x) + d(x)$ for a distance function, $\delta(e) \ge 0$. Tree edges have $w(u, x) + d(x) - d(u) = 0$.

For a walk $W$ from $s$ to $t$, let $\sigma(W)$ be the sequence of its non-tree edges, in order. Call a sequence $e_1, \ldots, e_j$ of sidetracks valid if the tail of $e_1$ is on $P(s)$, and the tail of each $e_{i+1}$ is on $P(\mathrm{head}(e_i))$.

(a) $\sigma$ is a bijection from $s$-$t$ walks to valid sequences. Between two consecutive sidetracks, and before the first and after the last, a walk uses only tree edges, and from any vertex there is exactly one tree edge; so the tree part from a vertex $y$ is a prefix of $P(y)$. Hence $\sigma(W)$ is valid, the last stretch is all of $P(\mathrm{head}(e_j))$ (it must end at $t$, and $P$ visits $t$ only at its end), and $W$ is determined by $\sigma(W)$. Conversely, a valid sequence gives the walk $P(s)$ up to the tail of $e_1$, then $e_1$, then $P(\mathrm{head}(e_1))$ up to the tail of $e_2$, and so on, ending with $P(\mathrm{head}(e_j))$; its sequence of non-tree edges is $e_1, \ldots, e_j$.

(b) $w(W) = d(s) + \sum_i \delta(e_i)$. Write $w(y, z) = (w(y, z) + d(z) - d(y)) + d(y) - d(z)$ for each edge of $W$. The terms $d(y) - d(z)$ telescope to $d(s) - d(t) = d(s)$, and the reduced costs are 0 on tree edges and $\delta(e_i)$ on sidetracks.

Step 4: the heaps. For $v \in R$, the heap $H_{\mathrm{out}}(v)$ has the sidetracks out of $v$, the cheapest at the root and the rest heap-ordered below it. $H_G(t)$ is built from $H_G$ of nothing by inserting the root of $H_{\mathrm{out}}(t)$ (if any), and for $v \ne t$, $H_G(v)$ is $H_G(\mathrm{next}(v))$ with the root of $H_{\mathrm{out}}(v)$ inserted (if any). Line L3 handles $v$ after $\mathrm{next}(v)$, so this is well defined, and since the insertion is persistent, $H_G(\mathrm{next}(v))$ is not changed. By induction along $P(v)$, $H_G(v)$ is a heap-ordered tree whose nodes are the roots of $H_{\mathrm{out}}(u)$ for the vertices $u$ of $P(v)$ (including $v$ and $t$) with nonempty $H_{\mathrm{out}}(u)$. Hang $H_{\mathrm{out}}(u)$ below its root in $H_G(v)$. The result, call it $\bar H(v)$, is a tree that contains every sidetrack whose tail lies on $P(v)$ exactly once, and it is heap-ordered: the children in $H_G(v)$ have keys at least their parent's by the heap property, and the rest of $H_{\mathrm{out}}(u)$ has keys at least its root's. Every node of $\bar H(v)$ has at most four children (two in the leftist heap, two in the array heap).

Step 5: states and walks. A state of the search is $(c, x, \sigma)$ where $x$ is a node of some $\bar H(v)$. Define the parent of a state created at line L9 to be the state removed in that iteration, and likewise at line L10. We show by induction over the order of creation that each state $(c, x, \sigma)$ satisfies:

(i) $\sigma, e(x)$ is a valid sequence, and $x$ is a node of $\bar H(v)$ where $v = s$ if $\sigma$ is empty and $v = \mathrm{head}$ of the last sidetrack of $\sigma$ otherwise;

(ii) $c = d(s) + \sum_{e \in \sigma} \delta(e) + \delta(e(x))$.

For the state of line L5, $x$ is the root of $\bar H(s)$ and $\sigma$ is empty, so both hold. A state made at line L9 from $(c, x, \sigma)$ has the same $\sigma$ and a child $y$ of $x$ in the same tree $\bar H(v)$, so (i) holds by Step 4, and its cost $c - \delta(x) + \delta(y)$ satisfies (ii). A state made at line L10 has the sequence $\sigma, e(x)$ and the root of $\bar H(\mathrm{head}(e(x)))$, whose sidetrack has its tail on $P(\mathrm{head}(e(x)))$, so (i) holds, and (ii) holds by adding $\delta$ of the root.

Now let $S$ be the set of all states that the rules can ever create (the tree of states under the parent relation, rooted at the state of line L5). The map $\phi(c, x, \sigma) = (\sigma, e(x))$ is a bijection from $S$ to the nonempty valid sequences. Onto: given a valid sequence $e_1, \ldots, e_j$, $e_1$ is at a unique node of $\bar H(s)$, reached from the root by a unique sequence of L9 moves; one L10 move goes to the root of $\bar H(\mathrm{head}(e_1))$, where $e_2$ is at a unique node, and so on. One-to-one: a state's history of moves can be read back from it: the number of L10 moves is the length of $\sigma$, the sidetracks of $\sigma$ name the nodes where those moves were made, and inside each tree the path from the root to a node is unique. So two different move histories give two different pairs $(\sigma, x)$.

By Step 3 and (ii), the cost of a state is the weight of the walk with the sidetrack sequence $\phi$ of the state. The tree walk $P(s)$ is the walk with the empty sequence, of weight $d(s)$, output at line L4.

Step 6: order of output. All moves have nonnegative cost: an L9 move costs $\delta(y) - \delta(x) \ge 0$ by heap order, and an L10 move costs $\delta(\text{root}) \ge 0$ by Step 3. So a state costs at least as much as its parent. The queue $Q$ holds, at the start of each iteration of line L6, exactly the states of $S$ not yet removed whose parent has been removed (and the root, before the first removal): this holds at line L5, and an iteration removes one state and inserts all its children (at most five), none of which has been seen before since each state has one parent. Every state of $S$ not yet removed has an ancestor in $Q$ (follow the parent links up to the first one not removed), whose cost is at most its own. Hence the state removed at line L7 costs at most every state not yet removed, and the costs removed form a nondecreasing sequence; each state is removed at most once.

Step 7: conclusion. The output is the tree walk followed by the walks of the removed states, in order. By Step 5 these are different walks, with their correct weights. The tree walk weighs $d(s)$, which is at most the weight of every walk by Step 3(b). By Step 6 the weights are nondecreasing, and when the loop stops with $k$ walks output, every walk not output is the walk of a state not removed, which costs at least the last cost removed. If the loop stops because $Q$ is empty, every state of $S$ was removed, so every $s$-$t$ walk was output, and $N$ is finite.

Termination. If $N < \infty$, $S$ is finite and every iteration removes one state, so the loop ends. Otherwise it ends after $k - 1$ iterations. Lines L1 to L4 are finite. $\blacksquare$