Negative Cycles: The Trap

A negative cycle does not guarantee distance = -∞ to all nodes. If the cycle is not reachable on the path to a target, the distance stays finite.

Example: Node $1$ → Node $5$ has distance $10$. A negative cycle exists between nodes $2$, $3$, $4$, but they are not on the $1$→$5$ path. Distance to $5$ is still $10$.

Check which nodes are affected before concluding -∞. Run BFS from each node in a negative cycle to mark all reachable nodes as having distance $-\infty$.