Bellman-Ford
Bellman-Ford makes no attempt to be clever about order. It sweeps the entire edge list and relaxes every edge; then it does it again, up to V−1 times in all. A shortest path uses at most V−1 edges, and each sweep is guaranteed to get at least one more edge of every shortest path right, so V−1 sweeps are enough. One more sweep that still improves something proves there is a negative cycle.
Its frontier
No frontier at all: the whole edge list, swept in order.
When it is the right choice
When an edge can be negative and Dijkstra is therefore not available: currency arbitrage, any cost that can be a refund, distance-vector routing. It is also the one to use when detecting a negative cycle is itself the goal. On a graph with no negative edges it is simply slower than Dijkstra for the same answer, so it is not a general-purpose replacement.
How it works
- Give the source a cost of zero and every other node a cost of infinity.
- Sweep the whole edge list, relaxing each edge: if going through it gives a cheaper cost, record it.
- Repeat the sweep up to V−1 times in total.
- Stop early if a whole sweep improves nothing, because nothing later will either.
- Run one more sweep. If it still improves something, a negative cycle exists and there is no shortest path.
Worth noticing
- The early exit is the difference between the worst case and the usual case. On most graphs a couple of sweeps settle everything and the third changes nothing; the passes counter says how many were actually needed, against the V−1 the bound allows.
- Load a graph with negative weights and compare this page with Dijkstra’s, which refuses it. That refusal is the honest one: Dijkstra would have produced a number, and the number would have been wrong.
- A negative cycle is not a failure of the algorithm, it is a property of the graph: you can go round it forever and keep getting cheaper, so no shortest path exists. This page says that rather than reporting the cost it happened to stop at.
Cost
- Best
- O(E)
- Average
- O(V · E)
- Worst
- O(V · E)
- Extra space
- O(V)
- Runs on
- a weighted undirected graph; a directed acyclic graph; a directed graph with a cycle
- Largest grid
- 11 by 7 cells
- Largest graph
- 14 nodes, 28 edges
The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.
Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.