Bellman-Ford Algorithm

Overview

Bellman-Ford solves the SSSP problem for graphs that may contain negative edge weights. The only restriction is that there be no negative-weight cycle reachable from the source (if one exists, shortest paths are undefined). The algorithm also explicitly detects negative cycles and reports failure.

Unlike Dijkstra, which selects vertices greedily, Bellman-Ford relaxes every edge $|V|-1$ times. This brute-force approach ensures distances propagate correctly along all possible simple paths.

Pseudocode

BELLMAN-FORD(G, w, s):
  for each v in G.V:
    v.d = ∞
    v.π = NIL
  s.d = 0
  for i = 1 to |G.V| - 1:
    for each edge (u, v) in G.E:          // in any order
      RELAX(u, v, w)
  // Negative cycle detection pass
  for each edge (u, v) in G.E:
    if v.d > u.d + w(u, v):
      return FALSE                         // negative cycle exists
  return TRUE

Why $|V|-1$ Iterations Suffice

A simple shortest path has at most $|V|-1$ edges (no vertex is repeated). Consider a shortest path $s = v_0 \to v_1 \to \cdots \to v_k = t$ with $k \le |V|-1$.

• After iteration 1: edge $(v_0, v_1)$ is relaxed, so $d[v_1] \le \delta(s, v_1)$. (In fact $d[v_1] = \delta(s, v_1)$ if no shorter alternative exists.)
• After iteration 2: edge $(v_1, v_2)$ is relaxed, so $d[v_2] \le \delta(s, v_2)$.
• …
• After iteration $k$: $d[t] \le \delta(s, t)$.

Since $k \le |V|-1$, after $|V|-1$ iterations all vertices have $d[v] = \delta(s, v)$. This can be formalised as dynamic programming: let $d^{(k)}[v]$ be the shortest path weight using at most $k$ edges. The recurrence $d^{(k)}[v] = \min(d^{(k-1)}[v], \min_{(u,v) \in E} \{d^{(k-1)}[u] + w(u,v)\})$ is exactly what the relaxation loop computes bottom-up.

Negative Cycle Detection

After $|V|-1$ passes over all edges, every $d[v]$ should equal $\delta(s, v)$ (or $\infty$ for unreachable vertices). If any edge can still be relaxed (i.e. $v.d > u.d + w(u,v)$ for some $(u,v)$), then:

• There exists a path of length $\ge |V|$ whose weight decreases from the current $d$ values.
• Such a path must contain at least $|V|$ edges, so it contains a cycle (by the pigeonhole principle).
• Removing that cycle cannot increase path weight (or the path wouldn’t be shorter), so the cycle must have negative total weight.

Thus a relaxable edge after $|V|-1$ passes indicates a negative-weight cycle reachable from $s$.

Important caveat: A negative cycle that is not reachable from $s$ will not be detected, because vertices in that component maintain $d = \infty$ throughout and no edge from a finite-distance vertex enters the component. This does not affect the SSSP result for reachable vertices.

Worked Example (No Negative Cycle)

Same graph as Dijkstra notes: $V = \{A,B,C,D,E,F,G\}$, source $E$. Weights: $E \to A:5$, $E \to F:7$, $E \to G:3$, $A \to B:1$, $A \to C:2$, $G \to F:3$, $C \to D:2$.

Processing edges in the order: (E,A), (E,F), (E,G), (A,B), (A,C), (G,F), (C,D).

Vertex	Init	$i=1$	$i=2$	$i=3\ldots6$
E	0	0	0	0
A	$\infty$	5 (E)	5	5
B	$\infty$	$\infty$	6 (A)	6
C	$\infty$	$\infty$	7 (A)	7
D	$\infty$	$\infty$	$\infty$	9 (C)
F	$\infty$	7 (E)	6 (G)	6
G	$\infty$	3 (E)	3	3

After $i=2$, all distances are final. Iterations 3-6 make no changes. Final check: no edge can be relaxed $\to$ return TRUE.

Worked Example (Negative Cycle)

Modify the graph: change $G \to F$ from 3 to $-4$, add edge $D \to A$ with weight $-7$, add edge $D \to C$ with weight $-2$. The cycle $A \to C \to D \to A$ has weight $2 + (-2) + (-7) = -7$ (negative).

Run Bellman-Ford. After $i=1$, $d[C]$ is set to 7 (via A). After $i=2$, $d[D]$ is set to 5 (via C), and $d[A]$ is set to $-2$ (via D). After $i=3$, $d[C]$ drops further, and so on. The values keep decreasing each iteration because the negative cycle propagates smaller distances indefinitely. After the full $|V|-1$ passes, the final check finds that some edge (e.g. $(D, A)$) can still be relaxed. The algorithm returns FALSE.

Early Termination and Practical Optimisations

• If a complete pass over all edges produces no changes, all distances are final. The algorithm can terminate early. This does not improve the worst case but helps on well-behaved inputs.
• Process edges in an order that respects topological order if the graph is a DAG (then only one pass is needed: DAG-SSSP in $\Theta(V+E)$).
• Use a queue of vertices whose $d$ value changed in the previous pass (Shortest Path Faster Algorithm, SPFA), which often runs faster in practice though its worst case remains $O(VE)$.

Running Time

• Initialisation: $\Theta(|V|)$.
• Main loop: $|V|-1$ iterations, each scanning all $|E|$ edges: $\Theta(|V| \cdot |E|)$.
• Final detection pass: $\Theta(|E|)$.
• Total: $\Theta(|V| \cdot |E|)$.

For dense graphs: $\Theta(|V|^3)$. For sparse graphs: $\Theta(|V|^2)$ if $|E| = \Theta(|V|)$.

Comparison

Property	Dijkstra	Bellman-Ford
Edge weights	Non-negative only	Any real
Negative cycle detection	No	Yes
Time complexity	$O((V+E)\log V)$	$\Theta(VE)$
Algorithm type	Greedy	Dynamic programming (implicit)
Practical use	Faster for $w \ge 0$	Necessary for negative edges

Summary

Property	Detail
Weight constraint	Any real numbers
Negative cycles	Detected on final extra pass
Why $V-1$ passes	Simple shortest path has $\le V-1$ edges
Time	$\Theta(V \cdot E)$
Space	$\Theta(V)$ beyond graph storage
Convergence check	No changes in a pass $\implies$ done

Past paper questions: y2026p1q9(c,d) (undetected negative cycles, purpose of extra relaxation pass, early termination optimisation).