Bellman-Ford negative-cycle detection

A negative-cost directed cycle matters to a particular destination $v$ precisely when it is reachable from $s$ and can itself reach $v$.^[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.

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.