Bellman-Ford Algorithm

A weighted directed graph $G = (V, E)$ with weight function $w: E \to \mathbb{R}$ may contain edges of negative weight. The single-source shortest-path problem asks, for a source vertex $s$, for the minimum total weight $\delta(s, v)$ of any path from $s$ to $v$, for every $v$. When all cycles reachable from $s$ have nonnegative total weight, this quantity is well defined for every vertex, and the shortest path can always be taken to be simple (no repeated vertices). But if some reachable cycle has negative total weight, an adversary can loop around it arbitrarily many times, driving the "shortest path" to $-\infty$. Detecting this situation is as important as computing distances. The mechanism relies on <a class="wiki-link" href="/wiki/cs-algo-edge-relaxation" data-track="wiki_article.body.wiki_link">Edge Relaxation and Optimal Substructure</a>: maintaining an estimate $d[v]$ for every vertex, initialized to $\infty$ except $d[s] = 0$, and repeatedly checking each edge $(u, v)$ with weight $w(u,v)$. If $d[u] + w(u,v) < d[v]$, the estimate $d[v]$ is improved to $d[u] + w(u,v)$, and $u$ is recorded as $v$'s predecessor. Relaxation never sets a distance too low — it only tightens an upper bound toward the truth — and shortest-path problems exhibit optimal substructure: a shortest path's prefixes are themselves shortest paths. Bellman-Ford exploits this by relaxing every edge in the graph, in an arbitrary fixed order, and repeating the sweep enough times for the correct distances to propagate everywhere, however tangled the graph's structure.

The key structural fact is: if the graph has no negative-weight cycle reachable from $s$, then every shortest path is simple and therefore has at most $V - 1$ edges. A single sweep over all edges relaxes every edge once; after $k$ sweeps, every shortest path of at most $k$ edges has been correctly computed (this is proved rigorously below). So $V-1$ sweeps suffice to correctly compute $d[v] = \delta(s,v)$ for all vertices, provided no negative cycle interferes. A final $V$-th pass checks for negative cycles: if any edge can still be relaxed, some shortest-path estimate has not stabilized, which is only possible if a negative cycle is reachable from $s$. ``` BELLMAN-FORD(G, w, s): // Initialization for each vertex v in G.V: d[v] = INFINITY pred[v] = NIL d[s] = 0 // Main relaxation phase: V - 1 passes for i = 1 to |G.V| - 1: for each edge (u, v) in G.E: if d[u] != INFINITY and d[u] + w(u, v) < d[v]: d[v] = d[u] + w(u, v) pred[v] = u // Negative-cycle detection pass for each edge (u, v) in G.E: if d[u] != INFINITY and d[u] + w(u, v) < d[v]: return "NEGATIVE CYCLE REACHABLE FROM s" return (d, pred) ``` A practical optimization: if an entire pass over all edges performs no relaxation, the distances have already converged, and the algorithm can terminate early — no further pass will change anything, by the same inductive argument used for correctness. This does not improve the worst-case bound but often helps in practice on graphs where distances stabilize quickly. To reconstruct an actual shortest path to a vertex $v$ (when no negative cycle blocks it), follow the `pred` pointers backward from $v$ to $s$; this traces a shortest path in reverse, by the same logic used in other predecessor-based shortest-path methods.

Time complexity. Initialization takes $O(V)$. The main phase runs $V-1$ passes, each of which relaxes every edge exactly once, costing $O(E)$ per pass, for $O(VE)$ total. The detection pass adds one more $O(E)$ sweep. Overall running time is

This is worst-case, best-case, and average-case identical in the standard formulation — the algorithm always performs the full $V-1$ passes regardless of input, unless the early-termination optimization is used, in which case the best case (distances converge in one pass, e.g. all edges from $s$ direct with no improving edges beyond) drops to $O(E)$, while the worst case remains $O(VE)$. Space usage is $O(V)$ for the distance array, predecessor array, and loop counters, plus the $O(V + E)$ storage of the graph itself, which is not attributable to the algorithm's auxiliary space.

Correctness — the core lemma. Let $\delta(s, v)$ denote the true shortest-path weight from $s$ to $v$, defined as $-\infty$ if a negative cycle on some path to $v$ exists, $\infty$ if $v$ is unreachable, and the ordinary minimum otherwise. Assume for now no negative cycle is reachable from $s$. Define $\delta_k(s,v)$ as the minimum weight of any path from $s$ to $v$ using at most $k$ edges. Claim: after the $k$-th pass of the main loop, $d[v] \le \delta_k(s,v)$ for every vertex $v$, and in fact $d[v] = \delta_k(s,v)$ once $\delta_k(s,v)$ equals the true shortest-path weight (which happens once $k$ reaches the number of edges in some shortest simple path to $v$). Proof by induction on $k$. Base case $k = 0$: before any pass, $d[s] = 0 = \delta_0(s,s)$ and $d[v] = \infty \ge \delta_0(s,v)$ for $v \ne s$ (since $\delta_0(s,v) = \infty$ for $v \ne s$, as zero edges cannot reach any vertex but $s$). This holds as equality trivially. Inductive step: suppose after pass $k$, $d[v] = \delta_k(s,v)$ for all $v$ (this stronger equality form holds by the same argument used for Edge Relaxation and Optimal Substructure applied repeatedly — relaxation never overestimates, and a straightforward induction shows it never underestimates either, so equality is maintained at each stage where the bound is tight). Consider any vertex $v$ and a shortest path $P$ using at most $k+1$ edges achieving $\delta_{k+1}(s,v)$. Let $u$ be the second-to-last vertex on $P$, and $(u,v)$ its last edge. The prefix of $P$ up to $u$ uses at most $k$ edges and, by optimal substructure, is itself a shortest such path, so its weight is $\delta_k(s,u)$. By the inductive hypothesis, $d[u] = \delta_k(s,u)$ before pass $k+1$ begins. Since pass $k+1$ relaxes edge $(u,v)$ (every edge is relaxed in every pass), afterward

Combined with the invariant that relaxation never produces an estimate below the true shortest-path weight (a standard fact: $d[v] \ge \delta(s,v) \ge \delta_{k+1}(s,v)$ is not quite what we want — rather one shows by induction that $d[v]$ is always the weight of some actual path from $s$ to $v$, hence $d[v] \ge \delta_k(s,v)$ can never be violated in the wrong direction), we obtain $d[v] = \delta_{k+1}(s,v)$ after pass $k+1$. This closes the induction. $\blacksquare$ Since no negative cycle is reachable from $s$, every shortest path is simple and has at most $V - 1$ edges, so $\delta_{V-1}(s,v) = \delta(s,v)$ for every vertex $v$. By the lemma, after $V-1$ passes, $d[v] = \delta(s,v)$ exactly — the algorithm is correct.

Correctness of negative-cycle detection. If no negative cycle is reachable from $s$, the argument above shows all $d[v]$ have converged to $\delta(s,v)$ after $V-1$ passes, and a further relaxation pass changes nothing — no edge $(u,v)$ can satisfy $d[u] + w(u,v) < d[v]$, since that would mean a path shorter than the true shortest path exists, a contradiction. So the detection pass correctly reports no negative cycle. Conversely, suppose a negative cycle $C = v_0 \to v_1 \to \cdots \to v_k = v_0$ is reachable from $s$. Suppose for contradiction that after the detection pass, $d[v_i] \le d[v_{i-1}] + w(v_{i-1}, v_i)$ holds for every edge of $C$ (no relaxation triggers). Summing these inequalities around the entire cycle gives

The sums of $d[v_i]$ on both sides are equal (they range over the same cyclic set of vertices), so they cancel, leaving

the total weight of the cycle. But $C$ is a negative cycle, so $w(C) < 0$, a contradiction. Hence at least one edge of $C$ must still be relaxable, and the detection pass correctly flags the negative cycle. This is a proof by contradiction resting on summing telescoping inequalities around the cycle.

Tradeoffs. Bellman-Ford's $O(VE)$ running time is markedly worse than Dijkstra's $O(E + V \log V)$ (with a Fibonacci heap) or $O(E \log V)$ (with a binary heap) on graphs with nonnegative weights. The price of handling negative weights and detecting negative cycles is this quadratic-in-the-worst-case blowup on dense graphs ($E = \Theta(V^2)$ gives $O(V^3)$). Bellman-Ford should be reserved for graphs where negative weights are actually possible; when weights are guaranteed nonnegative, Dijkstra is strictly preferable.

Consider a graph with source $s$ and vertices $A, B, C, D$, with directed edges: $s \to A$ (weight 6), $s \to B$ (weight 7), $A \to D$ (weight -2), $B \to A$ (weight -4), $B \to D$ (weight 8), $D \to C$ (weight -3), $C \to B$ (weight 3). Process edges in this fixed order every pass: $s\to A$, $s\to B$, $A \to D$, $B\to A$, $B\to D$, $D\to C$, $C\to B$. Initial: $d[s]=0,\ d[A]=\infty,\ d[B]=\infty,\ d[C]=\infty,\ d[D]=\infty$.

There are 4 vertices besides the source among $\{A,B,C,D\}$, so $V=5$ and the main phase runs $V-1=4$ passes, exactly as tabulated. Notice the estimate for $A$ is still improving on pass 4 ($4 \to -6$), showing the need for the full $V-1$ passes rather than stopping early on appearance-only convergence. Now run the detection pass (pass 5) with the converged values $d[s]=0, d[A]=-6, d[B]=-2, d[C]=-5, d[D]=-2$:

• $s \to A$: $0 + 6 = 6 \not< -6$. OK.
• $s \to B$: $0 + 7 = 7 \not< -2$. OK.
• $A \to D$: $-6 + (-2) = -8 < -2$. Relaxable!

Since edge $A \to D$ can still be relaxed, the algorithm reports a negative cycle reachable from $s$. Indeed, tracing $A \to D \to C \to B \to A$ gives total weight $(-2) + (-3) + 3 + (-4) = -6 < 0$ — exactly the negative cycle the proof by contradiction predicted, and the reason distances kept dropping ($d[A]: 6 \to 3 \to 0 \to -6 \to \cdots$) without ever stabilizing.

Distance-vector routing protocols, most notably RIP, implement a distributed, asynchronous relative of Bellman-Ford: each router repeatedly exchanges distance estimates with neighbors and relaxes them, converging to shortest paths without any central authority computing the whole graph at once. This distributed structure is a direct descendant of the relaxation invariant proved above, adapted to a setting with no fixed pass order or global synchronization. Arbitrage detection in currency and commodities trading networks reduces to negative-cycle detection: taking the negative logarithm of exchange rates turns multiplicative profit into additive path weight, and a negative cycle corresponds exactly to a sequence of trades yielding guaranteed profit. Bellman-Ford is the standard tool for scanning such graphs. Systems solving difference constraints — systems of inequalities of the form $x_j - x_i \le c$, arising in scheduling, VLSI layout timing, and constraint-based type checking — are transformed into a graph where each constraint becomes a weighted edge, and Bellman-Ford both finds a feasible assignment and certifies infeasibility via a negative cycle. Bellman-Ford also serves as a building block for more advanced algorithms. It underlies Johnson's algorithm for all-pairs shortest paths, which reweights a graph's edges using Bellman-Ford's output to make all weights nonnegative, then runs Dijkstra from every vertex — a technique previewed by the broader landscape of All-Pairs Shortest Paths Overview. The relaxation idea itself, generalized to capacities and augmenting structures, resurfaces in flow-based methods such as the Ford-Fulkerson Method, where Bellman-Ford can be used to find augmenting paths with favorable termination guarantees (as in the Edmonds-Karp refinement).

:::quiz[What does it mean if, after V-1 passes, some edge (u, v) still satisfies d[u] + w(u,v) < d[v]?]

• The graph is disconnected
• The source vertex was chosen incorrectly
• A negative-weight cycle is reachable from the source ✓
• The algorithm needs to run Dijkstra instead

Ask the tutor: How does Johnson's algorithm use Bellman-Ford's output to reweight edges before running Dijkstra from every vertex?