Proofs: Bellman-Ford algorithm

Bellman-Ford returns the distances or a negative cycle full

This proof shows: correctness, termination.

Claim. Let $G = (V, E)$ be a directed graph with $n$ vertices, real weights $w$, and a source $s$. BELLMAN-FORD$(G, w, s)$ ends. If no cycle of negative weight is reachable from $s$, it returns nil for the cycle, $d[v] = \delta(s, v)$ for each $v$, and $d[v] = d[\pi[v]] + w(\pi[v], v)$ for each $v \ne s$ with $d[v] < \infty$. If such a cycle is reachable, it returns a cycle of $G$ of negative weight.

Termination. Each loop has a fixed bound: $n - 1$ passes of $m$ edges, then at most $m$ edges, $n$ steps of line L11 and at most $n$ steps of line L12 (justified in Step 4). So the algorithm ends.

Notation. $\delta_k(v)$ is the least weight of a walk from $s$ to $v$ with at most $k$ edges ($\infty$ if there is none). $d_k[v]$ is the value of $d[v]$ at the end of pass $k$, with $d_0$ the values after line L2.

Step 1: every finite estimate is the weight of a walk, so $d[v] \ge \delta(s, v)$. This is the upper-bound property: at the start only $d[s] = 0$ is finite, and line L7 sets $d[v] = d[u] + w(u, v)$ with $d[u]$ finite, the weight of a walk to $u$ plus one edge. The same holds for the relaxation in line L11.

Step 2: $d_k[v] \le \delta_k(v)$ for $0 \le k \le n - 1$ (as long as the passes run). By induction on $k$. For $k = 0$, $\delta_0(s) = 0 = d_0[s]$ and $\delta_0(v) = \infty$ for $v \ne s$. For $k \ge 1$, take a walk $W$ to $v$ with at most $k$ edges and weight $\delta_k(v) < \infty$ (if $\delta_k(v) = \infty$ there is nothing to show). If $W$ has fewer than $k$ edges, $d_k[v] \le d_{k-1}[v] \le \delta_{k-1}(v) = w(W)$ by the hypothesis, because estimates never increase. Else $W$ is a walk $W'$ to some $u$ with $k - 1$ edges, then the edge $(u, v)$. By the hypothesis, $d_{k-1}[u] \le w(W')$, so at the moment pass $k$ relaxes $(u, v)$, $d[u] \le w(W')$ is finite. After line L6 and L7, $d[v] \le d[u] + w(u, v) \le w(W)$. Later steps of the pass only lower $d[v]$. So $d_k[v] \le w(W) = \delta_k(v)$. If line L8 stops the loop early after pass $k$, then no edge was tense in pass $k$, so the values do not change in any later pass, and the bound $d[v] \le \delta_j(v)$ holds for all $j$; Step 3 uses this.

Step 3: no reachable negative cycle. Then for each reachable $v$, a shortest walk can be chosen without a repeated vertex: removing a cycle from a walk does not increase its weight, because each cycle has weight at least $0$. So $\delta(s, v) = \delta_{n-1}(v)$. By Steps 1 and 2, $d[v] = \delta(s, v)$ at the end of the passes, also when line L8 stops early. Now each edge $(u, v)$ with $d[u] < \infty$ has $d[v] = \delta(s, v) \le \delta(s, u) + w(u, v) = d[u] + w(u, v)$, so the check of line L10 fails for every edge, and line L13 returns nil. When line L8 returns, the same values are returned. For $v \ne s$ with $d[v] < \infty$: when line L7 last set $d[v]$, it set $\pi[v] = u$ with $d[v] = d[u] + w(u, v)$ at that time; afterwards $d[u]$ can only decrease, so $d[u] + w(u, v) \le d[v]$, and if it were strictly less, the edge $(u, v)$ would be tense at the end, which we excluded. So $d[v] = d[\pi[v]] + w(\pi[v], v)$. Following $\pi$ from $v$ then gives a walk whose weight telescopes; since $d[s] = 0$ and all values are finite, the walk ends at $s$ (a predecessor cycle would have weight $0$ by telescoping, but Step 5 shows that every predecessor cycle has negative weight, so there is none). Thus the predecessor edges form a shortest-path tree.

Step 4: a reachable negative cycle is always found. Let $C = \langle c_0, c_1, \ldots, c_k = c_0 \rangle$ be a negative cycle reachable from $s$. Then pass $n - 1$ cannot have stopped early by line L8: that would mean no edge is tense, and the page on relaxation proves that some edge is tense after any finite sequence of relaxations when a negative cycle is reachable. For the same reason the check of lines L9 and L10 finds a tense edge $(u, v)$. Line L11 relaxes it, so now $d[v] < d_{n-1}[v] \le \delta_{n-1}(v)$ by Step 2.

We show that following $\pi$ from $v$ never reaches nil. Throughout the run, each vertex $x$ with $\pi[x] \ne$ nil satisfies

because the assignment of $\pi[x]$ makes it an equality, later only $d[\pi[x]]$ can fall while $\pi[x]$ stays, and a change of $d[x]$ also sets $\pi[x]$ again. Also $\pi[s] = $ nil implies $d[s] = 0$, because $d[s]$ changes only together with $\pi[s]$. Now assume the chain $v = x_0, x_1 = \pi[x_0], \ldots$ reaches nil without repeating a vertex, at $x_r$ with $\pi[x_r] = $ nil. All $x_i$ have finite estimates, so $x_r = s$ (every other vertex with a finite estimate has a predecessor), and $d[s] = 0$. Adding (A) along the chain gives $d[v] \ge d[s] + w(P) = w(P)$, where $P$ is the path $s = x_r \to \cdots \to x_0 = v$ with $r \le n - 1$ edges. So $d[v] \ge \delta_{n-1}(v)$, a contradiction. Hence the chain repeats a vertex. A chain with at most $n$ distinct vertices enters its cycle after at most $n - 1$ steps, so after the $n$ steps of line L11 the vertex $x$ lies on a cycle of predecessor edges, and line L12 follows $\pi$ from $x$ back to $x$ in at most $n$ steps.

Step 5: every cycle of predecessor edges has negative weight. Consider the moment a cycle $D = \langle y_0, y_1, \ldots, y_k = y_0 \rangle$ of predecessor edges ($\pi[y_i] = y_{i-1}$) first appears. It is created by a relaxation that sets $\pi[y_j] = y_{j-1}$ for one $j$. Just before it, the edge was tense: $d[y_{j-1}] + w(y_{j-1}, y_j) < d[y_j]$. For the other edges of $D$, (A) gives $d[y_{i-1}] + w(y_{i-1}, y_i) \le d[y_i]$. All these values are finite. Adding the $k$ inequalities, the sum of the $d$ values is the same on both sides, so $w(D) < 0$. The weight of $D$ does not depend on $d$, so $D$ stays negative while it exists. With Step 4, the cycle that line L12 returns has negative weight. $\blacksquare$