Bellman-Ford Algorithm
Find shortest paths from a source to all vertices, even with negative edge weights. Can also detect negative weight cycles.
Bellman-Ford Algorithm
Find shortest paths from a source to all vertices, even with negative edge weights. Can also detect negative weight cycles.
Initialize: source node 0 has distance 0, all others are ∞
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
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