Finds shortest paths and detects negative weight cycles
Time: O(VE)
Space: O(V)
Use Case: Graphs with negative weights, currency arbitrage detection
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Bellman-Ford Algorithm
The Bellman-Ford algorithm solves the single-source shortest path problem in graphs that may contain negative edge weights, something Dijkstra cannot handle. It also detects negative cycles, cycles whose total weight is below zero, which make shortest paths undefined.
How it works
Bellman-Ford relaxes every edge of the graph V - 1 times, where V is the number of vertices. Each pass propagates correct shortest distances one hop further, so after V - 1 passes all shortest paths of at most V - 1 edges are final. A final extra pass checks whether any edge can still be relaxed; if so, the graph contains a negative cycle reachable from the source. The running time is O(VE), slower than Dijkstra but far more general.
Applications
Bellman-Ford is used in distance-vector routing protocols such as RIP, in currency arbitrage detection where exchange rates become negative log weights, and in any planning problem where costs can be negative. Interview questions often test whether candidates know when Dijkstra fails and Bellman-Ford is required.