Shortest paths with negatives
When edges can carry negative weights, Dijkstra's greedy assumption breaks. The Bellman Ford algorithm handles negatives by giving up greed and simply relaxing every edge many times.
Relax everything, repeatedly
- Set the source distance to zero and all others to infinity.
- Make a pass over every edge, relaxing each one: if a shorter route through the edge exists, update the target distance.
- Repeat the full pass a number of times equal to the vertex count minus one.
After that many passes, every shortest path, which can use at most that many edges, has been found. Each pass extends the set of correctly settled distances by at least one more edge of path length.
Catching negative cycles
Run one extra pass. If any edge can still be relaxed to a smaller distance, the graph contains a negative weight cycle reachable from the source. Such a cycle makes shortest paths undefined, since looping it lowers cost without bound.
Bellman Ford is slower than Dijkstra because it touches every edge on every pass, but it is the right tool when negatives are present and it uniquely detects negative cycles.
Key idea
Bellman Ford relaxes every edge a number of times equal to vertices minus one, handling negative weights, and a final extra pass reveals any negative weight cycle.