Relax every edge
Bellman Ford finds shortest paths from a single source and tolerates negative edge weights. It relaxes every edge in the graph, then repeats that full sweep. After a number of sweeps equal to one less than the node count, all shortest paths are settled, because any simple path uses at most that many edges.
Detecting negative cycles
After the final sweep, run one extra pass over all edges. If any edge can still be relaxed to a smaller distance, the graph contains a negative cycle reachable from the source. Such a cycle means there is no well defined shortest path, since looping reduces cost without limit.
- Sweep all edges, relaxing distances.
- Repeat until paths stabilize.
- One more sweep that still improves signals a negative cycle.
Key idea
Bellman Ford relaxes every edge across repeated sweeps to handle negative weights, and a final sweep that still improves a distance proves the existence of a reachable negative cycle.