Bellman–Ford Algorithm
Shortest paths from a source that tolerates negative edges, and detects negative cycles.
Open on GeeksforGeeks ↗Intuition
Forget clever ordering — just relax every edge, over and over. After one full pass, all shortest paths using at most one edge are correct; after two passes, at most two edges; and since no shortest path can use more than V−1 edges, V−1 passes settle everything. If a V-th pass still improves something, that path is being fed by a negative cycle.
Relax every edge V-1 times. A shortest path has at most V-1 edges, and each pass guarantees one more edge's worth of correctness. Unlike Dijkstra it tolerates negative weights, and a V-th pass that still improves something proves a negative cycle exists.
Approach
Relax everything, V−1 times
For each pass, loop over every edge (u, v, w) and apply dist[v] = min(dist[v], dist[u] + w). No priority queue and no ordering assumptions.
Why V−1 passes suffice
A shortest path is simple, so it has at most V−1 edges. Pass k fixes all paths of k edges, so after V−1 passes every shortest path is final.
Negative cycle detection
Run one extra pass. If any edge still relaxes, some path can be made arbitrarily cheap by looping — report a negative cycle rather than a distance.
Solution & live demo
Common pitfalls
Skipping the extra detection pass
return dist
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None
return distAfter V-1 passes all genuine shortest paths are final, so any further improvement can only come from a cycle of negative total weight. Without that check the returned distances are meaningless on such graphs.
Relaxing from an unreachable vertex
if dist[u] + w < dist[v]:
if dist[u] != INF and dist[u] + w < dist[v]:
In Python inf + w stays inf so it happens to be safe, but in C++/Java adding to a large sentinel overflows to a negative number and floods the array with bogus distances. Guard the source explicitly.
Running only V-1 passes without the early exit
for _ in range(n - 1):
for u, v, w in edges: ...changed = False
...
if not changed:
breakCorrect but wasteful — most graphs settle long before V-1 passes. The changed flag turns the worst-case bound into a typical-case fast exit at no cost to correctness.
Edge cases
The extra pass still improves — report it; distances are meaningless.
If a pass changes nothing, distances are final — break out early.
Stays ∞; guard against ∞ + w overflow in languages without float infinity.