Bellman-Ford Algorithm
Software Engineer path · lesson 25 of 99Find shortest paths from a source to all vertices, even with negative edge weights. Can also detect negative weight cycles.
Directed and weighted; negative weights allowed, like A>B -2.
Pass 1 · badges show the current distance from the source.
Source S: distance 0, everything else ∞.
- 1dist[src] = 0; dist[others] = ∞
- 2repeat n - 1 times:
- 3 for (u, v, w) in edges:
- 4 if dist[u] + w < dist[v]: dist[v] = dist[u] + w
- 5 (stop early if nothing changed)
- 6for (u, v, w) in edges: if dist[u] + w < dist[v]: negative cycle
- Relaxations tried
- 0 / 18
- Improvements
- 0 / 7
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Run Bellman-Ford
Order the phases of the algorithm.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
Why does Bellman-Ford run V-1 iterations?
The short version
Imagine rumor spreading in a social network. Each round, everyone tells their neighbors what they've heard. After enough rounds, the shortest path (fewest retellings) stabilizes. Unlike Dijkstra, it works even if some rumors 'reduce' distance (negative weights).
In more depth
Edge Relaxation
For each edge (u, v, weight):
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weightAlgorithm
When to Use
When to reach for this
- Shortest path with negative edges
- Need to detect negative cycles
- Limited number of edges/hops allowed
- Arbitrage detection in currency exchange
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required