ƒ(x) GraphAdvanced interactive
Bellman-Ford
Shortest paths that tolerate negative edges.
graph_bellman-ford
step 1 / 11
dist[A] = 0, all others ∞. Relax every edge, repeat V−1 = 5 times.
relaxingcurrentvisitedshortest path
speed1×
How it works
Bellman-Ford finds shortest paths from a source by relaxing every edge, repeated V−1 times. Slower than Dijkstra, but it handles negative edge weights and detects negative cycles — a relaxation on the V-th pass means no shortest path exists.
Mental models
- After V−1 full passes every shortest path is final (paths have ≤ V−1 edges).
- A relaxation on one more pass exposes a negative cycle.
Common pitfalls
- Much slower than Dijkstra — only reach for it when edges can be negative.
Complexity
- Time
- O(V · E)
- Space
- O(V)
Reach for it when
- Negative-weight graphs
- Currency arbitrage
- Routing (RIP protocol)