Bellman-Ford Computes Shortest Paths in \(n - 1\) Rounds
Statement
Let \(G = (V, E)\) be a directed graph with \(|V| = n\), edge weights \(w : E \to \mathbb{R}\) (any sign), and source \(s \in V\). Run Bellman-Ford: for \(k = 1, \dots, n - 1\) rounds, relax every edge.
If no negative-weight cycle is reachable from \(s\), then after the \((n - 1)\)-th round, \(D[v] = d(v)\) for every vertex \(v\), where \(d(v)\) is the true shortest-path distance from \(s\) to \(v\) (Bellman 1958; Ford 1956; Kleinberg and Tardos 2005).
If a negative cycle is reachable from \(s\), the algorithm correctly reports it on the post-loop edge sweep.
Setup
Initialize \(D[s] = 0\), \(D[v] = +\infty\) for \(v \ne s\). A relaxation of edge \((u, v)\) with weight \(w(u, v)\) is the assignment \[ D[v] \leftarrow \min(D[v], D[u] + w(u, v)). \] A round of Bellman-Ford performs one relaxation of every edge in \(E\), in arbitrary order.
Let \(\delta_k(v)\) denote the length of the shortest walk from \(s\) to \(v\) that uses at most \(k\) edges, with \(\delta_k(v) = +\infty\) if no such walk exists.
Key invariant
Invariant. After \(k\) rounds, \(D[v] \le \delta_k(v)\) for every \(v\).
This holds because at round \(k\) we have already relaxed every edge \(k\) times; in particular, the last edge of any optimal \(\le k\)-edge walk to \(v\) has been relaxed at the right time to propagate the bound.
Proof by induction on \(k\)
Base case (\(k = 0\)): no rounds have been run. The only walk of length \(0\) from \(s\) is \(s\) itself, so \(\delta_0(s) = 0 = D[s]\) and \(\delta_0(v) = +\infty = D[v]\) for \(v \ne s\). The invariant holds.
Inductive step. Assume the invariant holds after round \(k - 1\): \(D[v] \le \delta_{k-1}(v)\) for every \(v\).
Let \(v \in V\) and consider any walk \(W\) from \(s\) to \(v\) using at most \(k\) edges with total weight \(\delta_k(v)\) (assume one exists; otherwise \(\delta_k(v) = +\infty\) and the bound is vacuous).
Case 1. \(W\) has at most \(k - 1\) edges. Then \(\delta_k(v) \le \delta_{k-1}(v)\), and by the inductive hypothesis \(D[v] \le \delta_{k-1}(v) = \delta_k(v)\) already at the start of round \(k\). Relaxations only decrease \(D[v]\), so the invariant survives.
Case 2. \(W\) has exactly \(k\) edges. Let \((u, v)\) be the last edge of \(W\), so the prefix is a walk from \(s\) to \(u\) with \(k - 1\) edges and weight \(\delta_k(v) - w(u, v)\). The prefix’s weight is \(\ge \delta_{k-1}(u)\) by definition, so \[ \delta_{k-1}(u) \le \delta_k(v) - w(u, v). \]
By the inductive hypothesis, \(D[u] \le \delta_{k-1}(u)\) at the start of round \(k\). Round \(k\) relaxes every edge, including \((u, v)\), so after that relaxation \[ D[v] \le D[u] + w(u, v) \le \delta_{k-1}(u) + w(u, v) \le \delta_k(v). \]
Edge order within a round does not matter for the final bound: monotonicity of \(D[v]\) ensures the most-recent relaxation of \((u, v)\) uses a \(D[u]\) value that is no larger than the value used in the inductive argument. So \(D[v] \le \delta_k(v)\) at the end of round \(k\), as claimed.
(The reverse inequality $D[v] $ length of some walk holds because every \(D[v]\) value is achieved by an actual walk; this is preserved by every relaxation.)
Why \(n - 1\) rounds suffice
If no negative cycle is reachable from \(s\), then for every \(v\) with \(d(v) < +\infty\) there exists a simple shortest path from \(s\) to \(v\). (Any non-simple walk contains a cycle; if the cycle has non-negative weight, deleting it yields a no-longer walk.) A simple path uses at most \(n - 1\) edges, so \[ d(v) = \delta_{n - 1}(v). \]
By the invariant after \(n - 1\) rounds, \(D[v] \le \delta_{n - 1}(v) = d(v)\). The reverse inequality is automatic, so \(D[v] = d(v)\).
Negative cycle detection
After the \(n - 1\) main rounds, sweep through all edges once more and check whether any edge \((u, v)\) still admits a relaxation \(D[u] + w(u, v) < D[v]\).
Claim. Such a relaxation exists if and only if some negative-weight cycle is reachable from \(s\).
If a negative cycle is reachable from \(s\). Suppose cycle \(C = (v_1, v_2, \dots, v_\ell, v_1)\) has total weight \(W(C) < 0\) and there is a path from \(s\) to \(v_1\). If after \(n - 1\) rounds no edge of \(C\) admits a further relaxation, then for every consecutive pair on \(C\), \[ D[v_{i+1}] \le D[v_i] + w(v_i, v_{i+1}). \] Summing around the cycle, \[ \sum_{i=1}^\ell D[v_i] \le \sum_{i=1}^\ell D[v_i] + W(C), \] which forces \(W(C) \ge 0\) — a contradiction. So at least one edge of \(C\) admits a relaxation.
If no negative cycle is reachable. Then \(D[v] = d(v)\) after \(n - 1\) rounds for every \(v\), and shortest-path distances satisfy the triangle inequality \(d(v) \le d(u) + w(u, v)\) for every edge \((u, v)\), so no further relaxation is possible.
Complexity
Each of the \(n - 1\) rounds performs one relaxation per edge, costing \(\Theta(m)\), plus the post-loop detection sweep of \(\Theta(m)\). Total: \(\Theta(n \cdot m)\).
The bound is tight in the worst case: the graph that is a single chain \(s \to v_1 \to v_2 \to \dots \to v_{n-1}\) with edges examined in the reverse order of the chain forces the algorithm to use all \(n - 1\) rounds before \(D[v_{n-1}]\) stabilizes.
Why each individual edge is relaxed every round
The argument requires every edge to be relaxed once per round, in arbitrary order. This is the key reason Bellman-Ford works on negative weights where Dijkstra does not: Dijkstra carefully processes vertices in non-decreasing \(D\)-order, but that order is not well-defined when negative edges exist (a “small” \(D[u]\) today may shrink further tomorrow). Bellman-Ford pays for this by repeatedly examining every edge — \(n - 1\) times instead of essentially once — but in exchange handles arbitrary signed weights.