Proofs: Goldberg's scaling algorithm

Goldberg's scaling algorithm is correct full

This proof shows: correctness, termination.

Claim. Let $G$ have integer weights and source $s$. GOLDBERG-SCALING ends. It returns NEGATIVE-CYCLE if and only if a negative cycle is reachable from $s$. Otherwise it returns $\delta(s, v)$ for every $v$ ($+\infty$ if $s$ does not reach $v$) and parents that form a shortest-path tree.

Let $R$ be the set of vertices reachable from $s$ and $G_R$ the subgraph on $R$ kept by line L1. Every walk from $s$ stays in $R$, so distances from $s$ are the same in $G$ and $G_R$, and a cycle in $G_R$ is reachable from $s$. So it is enough to prove the claim for $G_R$ with "a negative cycle in $G_R$" in place of "a reachable negative cycle". Write $w_i(e) = \lceil w(e) / 2^{b - i} \rceil$ and $c(u, v) = w_i(u, v) + p(u) - p(v)$ during scale $i$.

Step 1: rounding. For every integer $w$ and $q = 2^{b-i}$, $\lceil w/q \rceil \ge 2 \lceil w / (2q) \rceil - 1$: write $x = w/q$; then $\lceil x/2 \rceil < x/2 + 1$, so $2 \lceil x/2 \rceil - 1 < x + 1$, and since the left side is an integer, it is at most $\lceil x \rceil$. Also $w_0(e) = \lceil w(e) / 2^b \rceil \ge 0$, because $w(e) \ge -N > -2^b$. And $w_i(e) \ge w(e) / 2^{b-i}$, so for every cycle $C$, $w_i(C) < 0$ implies $w(C) < 0$.

Step 2: start of a scale. Suppose that at the end of scale $i - 1$ (or at the start, for $i = 1$, with $p = 0$ and the weights $w_0 \ge 0$), $w_{i-1}(u, v) + p(u) - p(v) \ge 0$ for every edge. After line L3, with Step 1, $c(u, v) = w_i(u, v) + 2p(u) - 2p(v) \ge 2(w_{i-1}(u, v) + p(u) - p(v)) - 1 \ge -1$.

Invariant. During scale $i$, every reduced cost is an integer at least $-1$, and no step turns an edge with $c \ge 0$ into one with $c = -1$. So the set of improvable vertices never grows. Step 2 gives it at the start; Steps 4 and 5 show that each step keeps it.

Step 3: components and levels. If a strongly connected component of the admissible graph contains an edge $(u, v)$ with $c = -1$, a path of admissible edges from $v$ back to $u$ closes a cycle $C$ with reduced cost at most $-1$. Reduced costs telescope around a cycle, so $w_i(C) < 0$, and by Step 1, $w(C) < 0$: the report of line L5 is correct. Otherwise all admissible edges inside components cost 0, the contracted admissible graph is a DAG, and $d(v)$, the least cost of an admissible path ending at $v$ (the empty path costs 0), is well defined, at most 0, constant on each component, and satisfies $d(v) \le d(u) + c(u, v)$ for every admissible edge. An improvable vertex $v$ with a $-1$ edge $(u, v)$ has $d(v) \le d(u) - 1 \le -1$; the edge joins two components.

Step 4: the cut (line L7). Let $X = \{v : d(v) \le j\}$ with $j \le -1$. If $u \in X$ and $(u, v)$ is admissible, $d(v) \le d(u) \le j$, so $v \in X$: no admissible edge leaves $X$. Lowering $p$ by 1 on $X$ changes $c$ by $+1$ on edges entering $X$, by $-1$ on edges leaving $X$, and not at all otherwise. Edges leaving $X$ had $c \ge 1$, so they end with $c \ge 0$. So the invariant holds. Let $v$ be improvable with $d(v) = j$ and $(u, v)$ any edge with $c = -1$. Then $d(u) \ge d(v) + 1 = j + 1$, so $u \notin X$ and the edge now costs 0. So every improvable vertex of level $j$ stops being improvable.

Step 5: the path step (lines L8 to L10). Let $v^*$ have the least level $-L$, and let $P$ be an admissible path in the contracted DAG achieving it; its edges cost 0 or $-1$, and exactly $L$ of them cost $-1$. Let $x_1, \ldots, x_L$ be their heads in order along $P$. Inside each component, admissible edges cost 0, so $P$ extends to a walk in $G_R$ through the same $-1$ edges; for $j \le i$, the part of this walk from $x_j$ to $x_i$ has reduced cost $-(i - j)$.

Let $c^+ = \max(c, 0)$ and $D(v) = \min(0, \min_j (\mathrm{dist}^+(x_j, v) - j))$, where $\mathrm{dist}^+$ is the distance with lengths $c^+$. These lengths are nonnegative integers and $-L \le D \le 0$, so Dial's buckets $-L, \ldots, 0$ compute $D$ exactly. $D$ is the distance from a virtual source with edges of length $-j$ to $x_j$ and 0 to every vertex, so $D(v) \le D(u) + c^+(u, v)$ for every edge. After $p \leftarrow p + D$, the new reduced cost is $c'(u, v) = c(u, v) + D(u) - D(v) \ge c(u, v) - c^+(u, v)$, which is $\ge 0$ if $c(u, v) \ge 0$ and $\ge -1$ if $c(u, v) = -1$. So the invariant holds.

Now assume $G_R$ has no negative cycle, and let $(y, x_j)$ be an edge with $c = -1$. We show $c'(y, x_j) \ge 0$, that is, $D(y) \ge D(x_j) + 1$. Since $D(x_j) \le -j$, it is enough to show $D(y) \ge 1 - j$. The term 0 is at least $1 - j$ as $j \ge 1$. For $i < j$, $\mathrm{dist}^+(x_i, y) - i \ge -i \ge 1 - j$. For $i \ge j$, take a path $Q$ from $x_i$ to $y$ with $c^+(Q) = \mathrm{dist}^+(x_i, y)$ (if there is none, the term is $\infty$). The walk from $x_j$ to $x_i$, then $Q$, then the edge $(y, x_j)$ is a closed walk with reduced cost at most $-(i - j) + c^+(Q) - 1$; it splits into cycles, each with $w_i \ge 0$ (by Step 1, a cycle negative for $w_i$ is negative for $w$), and reduced costs telescope, so this is at least 0. Hence $\mathrm{dist}^+(x_i, y) \ge i - j + 1$, and the term is at least $1 - j$. So, without a negative cycle, every $x_j$ stops being improvable, and line L10 never fires. Contrapositively, when line L10 fires, $G_R$ has a negative cycle, and the report is correct.

Step 6: progress. Let $k$ be the number of improvable vertices. If some level holds at least $\sqrt k$ of them, Step 4 fixes at least $\sqrt k$. Otherwise each of the at most $L$ nonempty levels holds fewer than $\sqrt k$, so $L > k / \sqrt k = \sqrt k$; the $x_j$ are $L$ different improvable vertices (each is the head of a $-1$ edge, and they lie in different components because levels strictly decrease along $P$ at each $-1$ edge), and Step 5 fixes all of them. With the invariant, $k$ strictly decreases in every iteration that does not return, so the loop of line L4 ends, after at most $n$ iterations.

Step 7: no negative cycle. Assume $G_R$ has no negative cycle. By Steps 3 and 5 no report is made. Each scale ends with $c \ge 0$ on every edge, which is the hypothesis of Step 2 for the next scale. After scale $b$, $w_b = w$ (and if $b = 0$, no weight is negative and $p = 0$), so $w(u, v) + p(u) - p(v) \ge 0$ on every edge. For any path $Q$ from $s$ to $v$, its reduced length is $w(Q) + p(s) - p(v)$, the same shift for all paths to $v$. Dijkstra's algorithm with these nonnegative lengths gives the reduced distance $\delta(s, v) + p(s) - p(v)$ and a tree of reduced-shortest paths, which are shortest paths for $w$. Line L11 undoes the shift. Vertices outside $R$ keep $\infty$.

Step 8: a negative cycle. Assume $G_R$ has a negative cycle $C$. If the algorithm did not report, then by Step 7's argument it would end with $w(u, v) + p(u) - p(v) \ge 0$ on every edge, and summing around $C$ would give $w(C) \ge 0$, a contradiction. (When $b = 0$ there is no negative weight, so no negative cycle.) So it reports NEGATIVE-CYCLE, and by Steps 3 and 5 it reports only when a negative cycle exists.

Termination. There are $b$ scales, each loop ends by Step 6, and every line inside is a finite computation. $\blacksquare$