Bellman-Ford & DAG shortest paths

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:

1. INITIALIZE-SINGLE-SOURCE(G, s).
2. Repeat $|V|-1$ times: relax every edge $(u,v)\in E$.
3. 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 $\le i$ edges has its correct value. After $|V|-1$ passes, all of them do.

Running time is $O(VE)$: 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 $\delta$ and the triangle inequality would forbid any further relaxation — contradiction. Conversely, sum the relaxed inequalities around a cycle $c=\langle v_0,\dots,v_k=v_0\rangle$: $\sum v_i.d \le \sum v_{i-1}.d + \sum w$. The $d$-terms cancel (each vertex appears once on each side), leaving $0\le\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 $\Theta(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.