= Bellman-Ford negative-cycle detection
{c}
A negative-cost <directed cycle> matters to a particular destination $v$ precisely when it is reachable from $s$ and can itself reach $v$.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 17: Shortest Paths III: Bellman-Ford>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; MIT 6.006, Lecture 17, p. 1: cycle between source and destination; p. 4: reachable-cycle corollary]{ref} Repeating it $m$ times adds $m$ times its negative total cost to a route. Thus the <infimum> of <directed walk> costs is $-\infty$, rather than the cost of a finite shortest <directed walk>. The distinction is about <reachability>, not simply the presence of a negative <edge> or a negative-cost <directed cycle> anywhere in the <graph>.
Add $C\to A$ of weight $-4$ to the worked example. Now $A\to B\to C\to A$ has total weight $-2+3-4=-3$. Add also an isolated <vertex> $U$ with a <self-loop> of weight $-1$. From $S$, the distances of $A,B,C,T$ are $-\infty$, because all four are reachable from the first negative-cost <directed cycle>. The source retains distance $0$: no <directed edge> leads back to $S$. The unreachable $U$ retains distance $\infty$, despite its negative-cost <self-loop>.
\Image[/bellman-ford-negative-cycle-reachability.png]
{title=Relevant negative-cost <directed cycles>: descendants from a source become ancestors when every <directed edge> is reversed}
For example, $m$ extra laps before proceeding to $T$ give costs $7-3m$. This construction also shows why requiring a <directed path> with no repeated <vertices> would change the problem: only <directed walks> permit arbitrarily many laps. Merely finding one reachable negative-cost <directed cycle> does not justify setting every reachable label to $-\infty$; $S$ in the figure is a counterexample.
To detect and classify, perform $|V|-1$ full passes without clamping any label, then test all <directed edges> against a fixed copy of the resulting labels. Collect heads $v$ of <edges> $u\to v$ satisfying $d(u)<\infty$ and $d(u)+w_{uv}<d(v)$. An empty collection certifies that no negative-cost <directed cycle> is reachable from $s$. Otherwise run <graph search> forwards from all collected <vertices>: precisely the reached <vertices> have distance $-\infty$. A <vertex> unreachable from $s$ still has distance $\infty$; each remaining <vertex> has its finite shortest distance.
Why is this classification exact? Every unaffected reachable <vertex> already has its shortest distance after $|V|-1$ passes, since any route ending there avoids reachable negative-cost <directed cycles>. Thus it cannot be the head of a strict improvement, or be reached from such a head. Conversely, all <vertices> on a reachable negative-cost <directed cycle> have finite labels by that time. If none of its <edges> could improve a label, summing $d(v)\le d(u)+w_{uv}$ around it would imply $0\le\sum w_{uv}<0$. At least one of its heads is therefore collected, and the forward <graph search> reaches the entire <directed cycle> and every affected descendant. Detecting a <directed cycle> alone and marking its descendants are separate tasks; finite intermediate labels in the affected region are not answers.
Back to article page
