Why Use Bellman–Ford?
Dijkstra’s algorithm relies on nonnegative edge weights. When a directed graph has negative weights, a route that initially appears expensive may become cheaper after a later negative edge is used. Bellman–Ford handles negative edge weights by repeatedly scanning the edges and improving distance labels. It also records predecessor pointers so that a path, not only its cost, can be recovered.
Throughout, \(G=(V,E)\) is a finite directed graph with no loops or multiple edges, with a real weight \(w(u,v)\) assigned to each directed edge \((u,v)\). Oppositely directed edges may both occur. The source \(s\) is a specified vertex of a nonempty graph, and \(n=|V|\). A directed walk follows edge directions and may repeat vertices and edges. Its cost is the sum of its edge weights; the length-zero walk from \(s\) to itself has cost \(0\).
This walk-based definition matters when negative cycles occur: a walk can go around a negative cycle repeatedly, decreasing its cost each time. Bellman–Ford computes finite shortest-path distances when no negative cycle is reachable from \(s\). A negative cycle is a directed cycle whose total weight is negative. The algorithm below does not, by itself, establish that this condition holds; cycle detection is a separate issue.
Initialization and Relaxation
For each vertex \(v\), maintain a label \(d(v)\), intended to represent the best cost found so far from \(s\) to \(v\). Also maintain a predecessor pointer \(\operatorname{pred}(v)\), which is either a vertex or undefined. Initialize \(d(s)=0\), and set \(d(v)=\infty\) for \(v\ne s\). Initially all predecessor pointers are undefined.
A scan of the edges means relaxing each edge once in a chosen fixed order. Bellman–Ford makes \(n-1\) full scans, unless it terminates early after a scan that makes no changes. The updates are made in place: an improvement earlier in a scan can be used when relaxing another edge later in the same scan. Thus the result of a scan can depend on the chosen edge order, although the algorithm’s guarantee after \(n-1\) scans does not.
Set the source label to \(0\), all other labels to \(\infty\), and all predecessors to undefined.
In the chosen order, relax every directed edge. Record every improved label and its predecessor.
Make at most \(n-1\) full scans. If one complete scan makes no changes, stop early.
For a reachable target, follow predecessor pointers backward from the target to \(s\), then reverse the vertex sequence.
Why the Relaxation Step Is Sound
Proof. Initially, the only finite label is \(d(s)=0\), the cost of the length-zero walk at \(s\). Suppose the statement holds before an edge \((u,v)\) is relaxed. If the relaxation does not change a label, the existing finite labels still have their represented walks. If the relaxation changes \(d(v)\), then \(d(u)\) is finite and, by the assumption, is the cost of a walk from \(s\) to \(u\). Appending the edge \((u,v)\) gives a walk from \(s\) to \(v\) whose cost is \(d(u)+w(u,v)\), exactly the new label. By induction over the successive relaxations, the assertion holds throughout the algorithm. \(\square\)
Consequently, whenever a finite shortest-path distance exists, a finite label cannot be smaller than that distance: the label is the cost of an actual walk. The other part of the algorithm’s guarantee is that repeated scans find a minimum-cost walk when no negative cycle is reachable from \(s\). Under that assumption, a minimum exists: any repeated-vertex segment of a walk contains a closed walk, which can be removed without increasing cost when there are no reachable negative cycles. Thus a minimum can be attained by a simple path, and there are only finitely many such paths. The standard Bellman–Ford correctness theorem states that after \(n-1\) full scans, the labels equal the shortest-path distances and the predecessor pointers recover shortest paths. Its path-length induction proof is treated separately; the examples below show how the scans implement the method.
Worked Traces
Worked Example: A Path That Needs Four Scans
Let \(V=\{s,a,b,c,d\}\), with directed edges, weights, and scan order \((c,d):2,\ (b,c):3,\ (a,b):-2,\ (s,a):4,\ (s,b):5\). There is no directed cycle in this graph. We have \(n=5\), so the prescribed number of scans is \(n-1=4\).
Initially the labels in the order \((s,a,b,c,d)\) are \((0,\infty,\infty,\infty,\infty)\); all predecessors are undefined.
Scan 1: The edges \((c,d)\), \((b,c)\), and \((a,b)\) have tails with label \(\infty\), so they make no change. Relaxing \((s,a)\) gives \(0+4=4<\infty\), so \(d(a)=4\) and \(\operatorname{pred}(a)=s\). Relaxing \((s,b)\) gives \(0+5=5<\infty\), so \(d(b)=5\) and \(\operatorname{pred}(b)=s\). The labels are now \((0,4,5,\infty,\infty)\).
Scan 2: The first edge still has \(d(c)=\infty\), so it does not change \(d(d)\). For \((b,c)\), \(5+3=8<\infty\), giving \(d(c)=8\) and \(\operatorname{pred}(c)=b\). For \((a,b)\), \(4+(-2)=2<5\), giving \(d(b)=2\) and \(\operatorname{pred}(b)=a\). The edge \((s,a)\) offers \(0+4=4\), equal to its current label, and \((s,b)\) offers \(0+5=5\), which is not less than \(2\). The labels are \((0,4,2,8,\infty)\).
Scan 3: Relaxing \((c,d)\) gives \(8+2=10<\infty\), so \(d(d)=10\) and \(\operatorname{pred}(d)=c\). The next edge gives \(d(b)+3=2+3=5<8\), so \(d(c)=5\). The remaining edges do not improve their head labels: \(4+(-2)=2\) equals \(d(b)\), \(0+4=4\) equals \(d(a)\), and \(0+5=5\) is greater than \(d(b)=2\). The labels are \((0,4,2,5,10)\).
Scan 4: The first edge now gives \(5+2=7<10\), so \(d(d)=7\). The next edge offers \(2+3=5\), equal to \(d(c)\); the other three edges also fail to improve their head labels. The labels are \((0,4,2,5,7)\).
Check: A fifth scan would leave all labels unchanged: the edge candidates in scan order are \(5+2=7\), \(2+3=5\), \(4+(-2)=2\), \(0+4=4\), and \(0+5=5\). The predecessor chain to \(d\) is \(d\leftarrow c\leftarrow b\leftarrow a\leftarrow s\), giving the path \(s,a,b,c,d\). Its cost is \(4+(-2)+3+2=7\). The other route to \(d\), namely \(s,b,c,d\), has cost \(5+3+2=10\), confirming the smaller label.
Worked Example: Recording and Using Predecessors
Let \(V=\{s,a,b,c\}\), with directed edges and weights \((s,a):6,\ (s,b):5,\ (a,b):-4,\ (b,c):3,\ (a,c):8\), in that scan order. Here \(n=4\), so make at most \(3\) scans.
Start with labels \((0,\infty,\infty,\infty)\). In scan 1, \((s,a)\) gives \(0+6=6\), so \(d(a)=6\) and \(\operatorname{pred}(a)=s\). Then \((s,b)\) gives \(0+5=5\), so \(d(b)=5\) and \(\operatorname{pred}(b)=s\). Next, \((a,b)\) gives \(6+(-4)=2<5\), so \(d(b)=2\) and \(\operatorname{pred}(b)=a\). The edge \((b,c)\) gives \(2+3=5<\infty\), so \(d(c)=5\) and \(\operatorname{pred}(c)=b\). Finally, \((a,c)\) gives \(6+8=14\), which does not improve \(5\). The labels are \((0,6,2,5)\).
In scan 2, the candidates are \(0+6=6\) for \(a\), \(0+5=5\) for \(b\), \(6+(-4)=2\) for \(b\), \(2+3=5\) for \(c\), and \(6+8=14\) for \(c\). None improves its current label. Scan 3 makes the same tests and also changes nothing. The path to \(c\) is recovered by following \(c\leftarrow b\leftarrow a\leftarrow s\), giving \(s,a,b,c\).
Check: The cost of that path is \(6+(-4)+3=5\). The alternative \(s,b,c\) has cost \(5+3=8\), and the direct two-edge route \(s,a,c\) has cost \(6+8=14\). The label \(d(c)=5\) and its predecessor chain agree with the least of these route costs.
Worked Example: An Unreachable Vertex
Let \(V=\{s,a,b,z\}\), with directed edges and weights \((s,a):3,\ (a,b):-1,\ (s,b):5,\ (z,a):-10\), in that scan order. The edge \((z,a)\) points into the reachable part, but there is no directed route from \(s\) to \(z\). Since \(n=4\), the algorithm allows \(3\) scans.
Initialize the labels to \((0,\infty,\infty,\infty)\) in the order \((s,a,b,z)\). In scan 1, \((s,a)\) gives \(0+3=3\), so \(d(a)=3\) and \(\operatorname{pred}(a)=s\). Then \((a,b)\) gives \(3+(-1)=2\), so \(d(b)=2\) and \(\operatorname{pred}(b)=a\). The edge \((s,b)\) offers \(0+5=5\), which does not improve \(2\). The tail of \((z,a)\) has label \(\infty\), so that edge makes no change. The labels are \((0,3,2,\infty)\).
In scan 2, the candidates for \(a\), \(b\), and \(b\) are \(0+3=3\), \(3+(-1)=2\), and \(0+5=5\), respectively; none improves a label. The edge from \(z\) still cannot be used. Scan 3 repeats those tests, with no changes. Thus \(z\) remains unreachable, while the predecessor chain for \(b\) is \(b\leftarrow a\leftarrow s\).
Check: The path \(s,a,b\) has cost \(3+(-1)=2\), while the direct edge \(s\to b\) has cost \(5\). The edge \(z\to a\) cannot be part of any walk starting at \(s\), because no such walk can first reach \(z\). Leaving \(d(z)=\infty\) is therefore correct.
Limits, Efficiency, and a Common Mistake
Negative edge weights are allowed, but a reachable negative cycle changes what the output means. If such a cycle can also reach \(v\), a walk from \(s\) to \(v\) can travel around the cycle arbitrarily many times, so its costs are unbounded below. There is then no finite shortest-path distance to \(v\). Bellman–Ford’s \(n-1\) scans alone should not be taken as proof that all labels are shortest distances; the finite-distance guarantee requires the absence of a negative cycle reachable from the source.
A full scan examines every edge once, so \(n-1\) scans take \(O(nm)\) time, where \(m=|E|\). The labels and predecessor pointers take \(O(n)\) space. An implementation may stop early when a full scan changes no label, since the next scan would repeat the same tests and make no changes.
Common mistake: assuming one scan handles every path. Let \(V=\{s,a,b\}\), with edges \((a,b):-1\) and \((s,a):2\), scanned in that order. Initially the labels are \((0,\infty,\infty)\). On the first edge, \(d(a)=\infty\), so \((a,b)\) cannot improve \(d(b)\). On the second edge, \(0+2=2<\infty\), so \(d(a)\) becomes \(2\). After one scan, \(b\) still has label \(\infty\), even though the path \(s,a,b\) has cost \(2+(-1)=1\). A second scan processes \((a,b)\) with \(d(a)=2\), giving \(2+(-1)=1<\infty\). The correction is to repeat the scans, not to conclude that \(b\) is unreachable after the first one.
Check Your Understanding
For each question, state the edge order if a scan order is needed, and show the calculations that justify your answer.
- Why is \(d(s)\) initialized to \(0\), while the other labels are initialized to \(\infty\)?
- For \(V=\{s,a,b\}\) and edges \((s,a):4,\ (a,b):-3,\ (s,b):2\), scanned in that order, give the labels and predecessors after the first scan.
- What changes during a relaxation when \(d(u)+w(u,v)=d(v)\)? Why is a strict inequality used?
- Explain why an edge whose tail has label \(\infty\) cannot update its head during that relaxation.
- Give the condition needed for Bellman–Ford’s finite shortest-distance guarantee, and explain what a reachable negative cycle can do to walk costs.