Proofs: Goldberg-Radzik algorithm

The Goldberg-Radzik algorithm is correct full

This proof shows: correctness, termination.

Claim. Let $G$ have real weights and source $s$. GOLDBERG-RADZIK ends. It returns NEGATIVE-CYCLE if and only if a negative cycle is reachable from $s$. Otherwise it returns $d[v] = \delta(s, v)$ for every $v$ ($+\infty$ if $v$ is not reachable), and $d[v] = d[\pi[v]] + w(\pi[v], v)$ for every reachable $v \ne s$.

A pass is one iteration of the loop of line L2, numbered from 1. A vertex is scanned when lines L7 to L9 handle it, or when line L3 removes it from $B$ (which also clears its mark).

Step 1: labels are walk weights. Line L9 changes a label only along a tense edge, so the run relaxes tense edges only, as in the generic relaxation method. As there, each finite label $d[v]$ is the weight of a walk from $s$, labels never increase, and if no negative cycle is reachable, $d[v] \ge \delta(s, v)$ at all times.

Step 2: the cycle test is sound. The search of line L4 follows only edges $(u, v)$ with $d[u] < \infty$ and $w_d(u, v) \le 0$, and labels do not change during the search. If it closes a cycle $C$ with a tense edge, then $\sum_{(u, v) \in C} w_d(u, v) < 0$, and the potentials cancel around the cycle, so $w(C) = \sum w_d < 0$. All vertices of $C$ have finite labels, so they are reachable from $s$ (Step 1). So a reported cycle is a reachable negative cycle. (The implementation checks the lightest of parallel edges, whose reduced cost is at most that of the edge followed, so the same argument applies.)

Step 3: the labeled set. At the end of each pass, a vertex is labeled if and only if its label dropped after its last scan, or it was never scanned and its label is finite. Indeed, line L1 marks $s$, line L9 marks every vertex whose label drops, and a scan unmarks the vertex. Consequently, if $u$ is not labeled at the end of a pass, then for every edge $(u, v)$, $d[u] + w(u, v) \ge d[v]$: at the last scan of $u$ the edge was either not tense or relaxed (a vertex removed in line L3 has no tense edge at that moment), and since then $d[u]$ has not changed and $d[v]$ has not increased.

Step 4: pass property. Assume no negative cycle is reachable from $s$. Let $v$ be reachable and let $s = p_0, p_1, \ldots, p_k = v$ be a shortest path with $k \le n - 1$ edges; every prefix is a shortest path. We show by induction on $j$ that at the end of pass $j$ (or at the start, for $j = 0$), $d[p_j] = \delta(s, p_j)$. For $j = 0$, $d[s] = 0 = \delta(s, s)$ (it is at least $\delta(s, s) = 0$ by Step 1 and starts at 0). Suppose it holds for $j - 1$, and consider the moment $d[p_{j-1}]$ became $\delta(s, p_{j-1})$, at or before the end of pass $j - 1$. If $p_{j-1}$ is scanned after that moment in a pass up to $j - 1$, the scan leaves $d[p_j] \le \delta(s, p_{j-1}) + w(p_{j-1}, p_j) = \delta(s, p_j)$ (either the edge is relaxed, or it is not tense; for a removal in line L3, it is not tense). Otherwise $p_{j-1}$ is labeled at the end of pass $j - 1$ (Step 3), so it is in $B$ at the start of pass $j$. In pass $j$, line L3 either removes it, in which case the edge is not tense and $d[p_j] \le \delta(s, p_j)$ already, or keeps it, in which case it is in $A$ and is scanned in pass $j$ with the label $\delta(s, p_{j-1})$, which cannot fall further; that scan gives $d[p_j] \le \delta(s, p_j)$. With Step 1, $d[p_j] = \delta(s, p_j)$ from then on.

Step 5: no negative cycle. Assume no negative cycle is reachable. By Step 2, the cycle test never fires. By Step 4, at the end of pass $n - 1$ (if the algorithm runs that long) every reachable vertex has its final label, so no edge out of a reachable vertex is tense; at the start of pass $n$ line L3 removes every vertex of $B$, $A$ is empty, and the pass-count test does not fire. So NEGATIVE-CYCLE is never returned, and the loop ends after at most $n$ passes (each pass is finite, since the search and the scans are). When it ends, $B$ is empty, so no vertex is labeled, and by Step 3 no edge out of a vertex with finite label is tense. Adding $d[p_{i+1}] \le d[p_i] + w(p_i, p_{i+1})$ along a shortest path gives $d[v] \le \delta(s, v)$, so $d[v] = \delta(s, v)$ with Step 1. Unreachable vertices are never relaxed and keep $\infty$. For $v \ne s$ reachable, $\pi[v]$ was set with $d[v]$ at its last drop, when $d[v] = d[\pi[v]] + w(\pi[v], v)$ with the then label of $\pi[v]$, which is at least the final one; the edge is not tense at the end, so equality holds.

Step 6: a reachable negative cycle is reported. Assume a negative cycle $C$ is reachable from $s$. Suppose the loop ends with $B$ empty. By Step 3 no edge out of a vertex with finite label is tense. Every vertex on a path from $s$ then has a finite label (induction along the path), so $d[c_{i+1}] \le d[c_i] + w(c_i, c_{i+1})$ around $C$, and adding gives $0 \le w(C) < 0$, a contradiction. So the loop does not end with $B$ empty. Each pass is finite, so pass $n$ is reached unless NEGATIVE-CYCLE is returned earlier; in pass $n$ the set $B$ is nonempty, and by the same contradiction some vertex of $B$ has a tense edge (otherwise line L3 empties $B$, and then $A$ is empty and the next $B$ is empty). So $A \ne \emptyset$ and line L5 returns NEGATIVE-CYCLE. With Step 2, the algorithm returns NEGATIVE-CYCLE exactly when a negative cycle is reachable.

Steps 5 and 6 give the claim, and both show termination. $\blacksquare$