When edges go negative
Dijkstra breaks when edges can be negative. The Bellman Ford algorithm handles negative edge weights and even detects negative cycles, loops whose total weight is below zero and would let a path shrink without bound.
Relax everything, repeatedly
Instead of greedily settling one vertex at a time, Bellman Ford relaxes every edge in each pass.
- Set the source distance to zero and all others to infinity.
- Repeat this many times, one fewer than the vertex count: for every edge, try to shorten the destination distance using the source distance plus the edge weight.
After enough passes, all shortest distances are correct, because any shortest path uses at most one fewer edge than the vertex count.
Catching negative cycles
Run one extra pass. If any distance still improves, a negative cycle is reachable, so no finite shortest path exists for the affected vertices. This detection is a feature Dijkstra cannot offer.
The cost is higher than Dijkstra: it relaxes all edges across many passes, giving a running time proportional to vertices times edges.
Key idea
Bellman Ford relaxes all edges across repeated passes to tolerate negative weights, and one extra pass reveals any negative cycle.