Bellman-Ford & DAG shortest paths

◈ 4 cards

Bellman-Ford handles negative weights and detects negative cycles in O(VE); DAG-SHORTEST-PATHS does it in Θ(V+E) via topological order.

Bellman-Ford: relax everything, |V|−1 times

Bellman-Ford solves single-source shortest paths even when edges are negative, and it detects a reachable negative cycle (in which case no finite answer exists). The algorithm:

INITIALIZE-SINGLE-SOURCE(G, s).
Repeat $∣ V ∣ - 1$ times: relax every edge $(u, v) \in E$ .
One more pass: if any edge can still be relaxed (v.d > u.d + w(u,v)), return FALSE — a negative cycle is reachable. Otherwise return TRUE.

Why $∣ V ∣ - 1$ passes? A shortest path in a graph with no negative cycle is simple — at most $∣ V ∣ - 1$ edges. By the path-relaxation property, after pass $i$ every shortest path using $\leq i$ edges has its correct value. After $∣ V ∣ - 1$ passes, all of them do.

Running time is $O (V E)$ : each of the $∣ V ∣ - 1$ passes scans all $∣ E ∣$ edges.

Worked correctness of the negative-cycle check

Suppose after the passes some edge $(u, v)$ still satisfies v.d > u.d + w(u,v). If there were no negative cycle, every reachable vertex would already hold $δ$ and the triangle inequality would forbid any further relaxation — contradiction. Conversely, sum the relaxed inequalities around a cycle $c = ⟨ v_{0}, \dots, v_{k} = v_{0} ⟩$ : $\sum v_{i} . d \leq \sum v_{i - 1} . d + \sum w$ . The $d$ -terms cancel (each vertex appears once on each side), leaving $0 \leq \sum w (c)$ . So a still-relaxable edge means $\sum w (c) < 0$ — a negative cycle.

DAG shortest paths: one pass in topological order

If the graph is a DAG there are no cycles at all (hence no negative cycles), so you don't need $∣ V ∣ - 1$ passes — one pass suffices. Topologically sort the vertices, then relax each vertex's out-edges in that order. Because a topological order processes every predecessor of $v$ before $v$ , all paths into $v$ are accounted for by the time you relax out of it. This runs in $Θ (V + E)$ and handles negative weights freely (great for PERT / critical-path scheduling — negate weights for longest path).

Worked example

On the CLRS Fig 22.4 graph (vertices $s, t, x, y, z = 0, 1, 2, 3, 4$ , several negative edges, no negative cycle) Bellman-Ford from $s$ yields distances $[0, 2, 4, 7, - 2]$ . Add one more strongly negative edge to create a negative cycle and the algorithm reports it.

The exercise graph (s, t, x, y, z = 0–4). The negative edges x→t (−2) and y→x (−3) are harmless — Bellman-Ford handles them. The dashed edge z→t = −10 is the one the exercise adds afterwards: with t→z = −4 it forms the cycle t→z→t of weight −14, so δ(s,t) = −∞ and the extra pass returns FALSE.

Bellman-Ford on the graph above (without the −10 edge), relaxing the edges in the order the exercise lists them. Highlighted cells changed during that pass: t drops to 2 in pass 2, z to −2 in pass 3. Pass 4 changes nothing, and the final row is the [0, 2, 4, 7, −2] the exercise prints.