Bellman-Ford finds shortest paths from a source to every other node even with negative edge weights — the case that breaks Dijkstra’s greedy assumption.

It achieves this by brute-force diligence: relax every edge V−1 times, trusting repeated passes to propagate the correct distances regardless of edge order. The same extra work that slows it also lets it detect negative cycles, which no finite shortest path can exist around.

How It Works

1. Initialize: dist[source] = 0, dist[v] = ∞ for all others.
2. Relax V−1 times: for each edge (u, v, w), if dist[u] + w < dist[v], update dist[v] and the parent.
3. Negative-cycle check: run one more pass. If any edge is still relaxable, a negative cycle is reachable — report it.

Key Insight

Any simple shortest path uses at most V−1 edges — a path with V edges must repeat a vertex, and a repeated vertex can be cut out. After V−1 rounds of relaxing all edges, every shortest path’s final edge has been considered.

Dijkstra finalizes each node once and can’t revisit it. Bellman-Ford never finalizes until the end, so a later-revealed negative edge can still lower an “already settled” distance. That robustness is exactly what costs O(VE).

Worked Example

Run Bellman-Ford on the visualizer’s negative-weight graph, source S:

Round 1 (relax every edge once):

• S→A(6): A=6; S→B(7): B=7; A→C(−2): C=4; A→D(5): D=11; B→C(8): no; B→D(−3): D=4; D→C(2): C=4 stays; C→T(9): T=13; D→T(4): T=8.

Round 2 (new improvements): D=4 → D→T(4): T=8 stays; B→D(−3) after B=7: D=4 already… T and all others unchanged.

Rounds 3–6: no further changes — distances have converged: S=0, A=6, B=7, C=4, D=4, T=8. In the visualizer, watch the distance table stop changing after the second round — that’s convergence before the V−1 budget runs out.

Negative Cycle Detection

If a negative cycle is reachable from the source, distances can shrink forever — each loop around the cycle lowers them again. The extra relaxation pass after V−1 rounds catches this: any edge still relaxable lies on or reaches such a cycle. Currency arbitrage is the classic use — log-transform exchange rates so a “negative cycle” corresponds to a profitable conversion loop.

Edge Cases & Pitfalls

• Negative cycle reachable — no well-defined shortest path exists. The algorithm reports it rather than returning garbage.
• Negative cycle not reachable from source — harmless: distances remain finite and correct.
• Converges early — on many graphs, distances stabilize after a few rounds. A real implementation can early-exit when a full round changes nothing — but even that round must scan every edge once, so the best case is O(E).
• Unreachable nodes — keep dist = ∞ and skip relaxing edges from unreachable sources.

Comparison: Bellman-Ford vs Dijkstra

Applications

• Currency arbitrage — detecting profitable exchange cycles
• Distance-vector routing — RIP and BGP are essentially distributed Bellman-Ford
• Shortest paths with negative costs — scheduling problems with penalty edges
• A building block — inside Johnson’s algorithm for all-pairs shortest paths

Practice Trajectory

1. Hand-relax all edges for one round on the visualizer’s graph and compare with the table.
2. Add a negative cycle and trace the detection pass flagging the affected nodes.
3. Compare Bellman-Ford’s final table with Dijkstra’s on a non-negative graph.
4. Explain why V−1 rounds are enough for any simple shortest path.
5. Implement Bellman-Ford with an early-exit when a round produces no changes.