negative-cycle detection

Suppose there is a loop in your road network where, every time you drive around it, the total cost goes DOWN — maybe a chain of currency trades that ends with more money than you started. If such a loop is reachable from the source, the idea of a 'shortest' path collapses: you could circle it forever, pushing the cost toward minus infinity. Negative-cycle detection is how an algorithm notices this and reports 'no finite answer' instead of returning nonsense.

The clean test piggybacks on Bellman-Ford. Recall that after V-1 relaxation passes, if there is no negative cycle, every distance estimate has reached its true value and no edge can be relaxed any further (the triangle inequality holds everywhere). So run one more, V-th, pass over all edges: if any edge (u, v) can STILL be relaxed — that is, d[u] + w(u,v) < d[v] is still true — then some shortest path estimate is still dropping after it should have settled, which can only happen if a negative cycle is reachable. To find the actual cycle, follow predecessor pointers back from the vertex whose estimate dropped; you will loop around the offending cycle. The whole test costs just one extra O(E) pass.

This matters anywhere a 'profit loop' would be a bug or an opportunity: arbitrage detection in finance, infeasibility checks in scheduling with deadlines, and as a safety check before trusting any shortest-path output on graphs with negative edges. A subtlety to keep straight: a negative cycle only poisons vertices that can reach it or be reached from it through the source; vertices in a separate, negative-cycle-free part of the graph still have well-defined shortest distances. Detection answers a yes/no question and locates the cycle, but it does not magically repair the problem — if a negative cycle exists on the routes you care about, there simply is no shortest path.