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.
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
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.