Where Dijkstra ran out of road
The previous guide ended on a warning: Dijkstra is fast precisely because it dares to finalize a vertex the moment it is pulled off the priority queue, never revisiting it. That gamble pays off only when all edge weights are non-negative, so that no path discovered later can ever be cheaper. The instant a negative edge exists, the gamble can lose: a vertex closed off early might have been reachable more cheaply through a path that dips down a negative edge afterward, and Dijkstra has already walked away. So we need a method that makes no such bet — one that is willing to keep improving an estimate no matter how late the improvement arrives.
Everything we need is already in hand from guide 1. Recall the single primitive: relaxing an edge (u, v) of weight w asks "is going to u and then crossing this edge cheaper than my current best guess for v?" — if dist[u] + w < dist[v], lower dist[v] to dist[u] + w and record u as v's predecessor. Relaxation is always safe: it never sets an estimate below the true shortest distance, and the true distances are a fixed point where no edge can be relaxed further. Dijkstra was one disciplined schedule of relaxations. Bellman-Ford is the opposite stance — it abandons cleverness about order entirely.
Just relax every edge, V-1 times
Here is the whole algorithm. Set dist[source] = 0 and every other dist to infinity. Then make a pass: go through all E edges, in any fixed order you like, and relax each one. Now do another full pass. And another. The Bellman-Ford algorithm runs exactly V-1 such passes (where V is the number of vertices), then stops. That is it — no priority queue, no visited set, no decisions about which vertex to process next. Brute, almost mindless, repetition.
for i in 1 .. V-1: # V-1 passes
for each edge (u, v, w): # all E edges, any order
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pred[v] = uWhy V-1, and why is that enough? The key fact, from guide 1, is that in a graph with no negative cycle a shortest path never needs to repeat a vertex, so it uses at most V-1 edges. Now watch the magic of doing full passes: after pass 1, dist is correct for every vertex whose shortest path is 1 edge long; after pass 2, correct for every vertex reachable by a 2-edge shortest path; and in general, after pass k, dist is correct for every vertex whose shortest path uses at most k edges. Since no shortest path exceeds V-1 edges, after V-1 passes every distance has settled. The proof is a clean induction on k — the next paragraph is exactly that argument.
- Base case (k = 0): before any pass, dist[source] = 0 is correct, the only vertex whose shortest path uses 0 edges.
- Inductive step: suppose after pass k-1 every vertex with a shortest path of at most k-1 edges has its correct distance. Take a vertex v whose shortest path uses exactly k edges; let its last edge be (u, v).
- Then u has a shortest path of k-1 edges, so dist[u] is already correct. Pass k relaxes every edge, including (u, v), which sets dist[v] = dist[u] + w — the true shortest distance.
- By induction, after V-1 passes all distances are correct, since no shortest path is longer than V-1 edges.
What a negative cycle even means
Notice the proof leaned hard on one phrase: "a shortest path never repeats a vertex." That is true only when there is no negative cycle — a cycle whose edge weights sum to a negative number. If such a cycle exists and is reachable from the source and can reach your target, then "shortest path" stops being a well-defined thing. Every time you loop around the cycle you subtract more weight, so you can drive the cost down without limit. There is no shortest path; there is only an infinite descent toward minus infinity. This is not a bug to be patched — it is a genuine feature of the input, and any honest shortest-path method must report it rather than return a meaningless number.
And this is no exotic edge case. Negative weights show up the moment edges model gains and losses rather than physical distance — arbitrage in currency exchange (does some loop of trades end with more money than it started?), profit-and-cost networks, or constraint systems where a contradiction surfaces precisely as a negative cycle. Asking "is there a negative cycle?" is often the entire point of the computation, not a corner case to dodge. Dijkstra cannot even ask the question. Bellman-Ford answers it almost for free.
The V-th pass: a free lie detector
Here is the elegant part. We proved that with no negative cycle, all distances are final after V-1 passes — meaning at that point no edge can be relaxed any further; the system has reached its fixed point. So run one more pass, the V-th. If during this extra pass some edge (u, v) still relaxes — that is, dist[u] + w < dist[v] is still true — then a distance just dropped after it was supposed to be frozen. The only thing that can keep pushing an estimate down forever is a negative cycle. So the rule for detecting it is dead simple: any successful relaxation on pass V proves a reachable negative cycle exists.
If you want to actually exhibit the offending cycle, not just know it exists, the predecessor pointers do the work. When an edge relaxes on the V-th pass at some vertex v, that v is reachable from a negative cycle. Walk backward through pred[] V times to be sure you have stepped onto the cycle itself, then keep following pred[] until you return to a vertex you have already seen — the vertices between the two visits spell out the cycle. It is the same predecessor chain that, in the normal case, reconstructs the shortest path itself; here it reconstructs the proof of impossibility.
The price, and the connections
Count the work honestly: V-1 passes (plus one detection pass), each touching all E edges, gives O(V*E). On a dense graph where E is around V^2 that is O(V^3) — markedly slower than Dijkstra's O(E + V log V). This is the trade you are buying: Bellman-Ford pays a real asymptotic premium for the ability to handle negative edges and to certify their cycles. As always, big-O hides constants and small-input behavior — on a tiny graph the simple double loop may beat Dijkstra's heap overhead — but for scaling, Dijkstra wins decisively when weights are non-negative. Use Bellman-Ford when you must, not by default.
Two practical refinements are worth knowing, with honest caveats. First, early termination: if a whole pass relaxes no edge, the fixed point is already reached and you can stop immediately — often far before V-1 passes. This helps enormously on typical inputs but does not change the worst-case O(V*E); an adversary can force all V-1 passes. Second, the queue-based variant (often called SPFA) only re-examines edges out of vertices whose distance just changed, which is usually much faster in practice — yet its worst case remains O(V*E), and on crafted graphs it offers no asymptotic improvement at all. Faster-on-average is not faster-in-the-worst-case; keep the two separate.
Finally, see where this sits in the wider story. Bellman-Ford is the negative-weight workhorse for single-source shortest paths, and it is also a crucial building block beyond that. In the next guide, when we attack the all-pairs problem on graphs with negative edges, Johnson's algorithm will run Bellman-Ford exactly once — not mainly to find distances, but to compute a clever reweighting that makes every edge non-negative, after which fast Dijkstra can be unleashed from every vertex. Bellman-Ford's willingness to cope with negativity is precisely what licenses that trick. Slow, simple, and honest, it is the tool that refuses to look away from the cases Dijkstra cannot face.