Reading a Bellman–Ford Trace
Bellman–Ford is useful when edge weights may be negative: unlike Dijkstra’s algorithm, it does not require all weights to be nonnegative. Its calculations are organized as repeated scans of the edges. A scan can change distance labels and predecessor pointers, so the edge order matters when tracing the algorithm by hand. In the examples below, each edge is scanned in the listed order, and every update takes effect immediately.
A weighted directed graph has a specified vertex set and directed edges, each assigned a real weight. Fix a source vertex \(s\). The label \(d(v)\) is the current estimate of the cost of a directed path from \(s\) to \(v\). Initialize \(d(s)=0\) and \(d(v)=\infty\) for every other vertex. For an edge \(u\to v\) of weight \(w\), relaxation replaces \(d(v)\) by \(d(u)+w\) if \(d(u)\) is finite and \(d(u)+w<d(v)\). When this strict improvement occurs, record \(u\) as the predecessor of \(v\).
The distinction between a negative edge and a negative cycle is important. A negative edge can lower the cost of a path without causing any difficulty: there may still be a least-cost path to every reachable vertex. A reachable negative cycle has a different effect. A walk can travel to the cycle, go around it repeatedly to reduce its cost, and then continue to a destination. We will see both situations in the calculations.
Negative Edges Without a Negative Cycle
Worked Example: Recovering a Shortest Path
Let the weighted directed graph have vertex set \(V=\{s,a,b,c,t\}\) and the following edges, listed in scan order, with weights shown in parentheses: \(s\to a\) (4), \(s\to b\) (5), \(a\to b\) (\(-2\)), \(a\to c\) (4), \(b\to c\) (3), \(b\to t\) (6), \(c\to t\) (1). Use \(s\) as the source.
Initially, \((d(s),d(a),d(b),d(c),d(t))=(0,\infty,\infty,\infty,\infty)\). In the first pass, \(s\to a\) gives \(d(a)=0+4=4\), and \(s\to b\) gives \(d(b)=0+5=5\). Then \(a\to b\) proposes \(4+(-2)=2<5\), so \(d(b)\) becomes \(2\). The edge \(a\to c\) gives \(d(c)=4+4=8\). Next, \(b\to c\) proposes \(2+3=5<8\), so \(d(c)=5\). The edge \(b\to t\) gives \(d(t)=2+6=8\), and \(c\to t\) proposes \(5+1=6<8\), so \(d(t)=6\).
The complete pass trace is:
| Point in the trace | \(d(s)\) | \(d(a)\) | \(d(b)\) | \(d(c)\) | \(d(t)\) |
|---|---|---|---|---|---|
| Initialization | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| After pass 1 | 0 | 4 | 2 | 5 | 6 |
| After pass 2 | 0 | 4 | 2 | 5 | 6 |
| After pass 3 | 0 | 4 | 2 | 5 | 6 |
| After pass 4 | 0 | 4 | 2 | 5 | 6 |
The graph has \(n=5\), so four passes are the prescribed \(n-1\) passes. On each later pass, none of the edges improves a label. The predecessor pointers are \(\operatorname{pred}(a)=s\), \(\operatorname{pred}(b)=a\), \(\operatorname{pred}(c)=b\), and \(\operatorname{pred}(t)=c\). Following them backwards from \(t\) and reversing the sequence gives the path \(s,a,b,c,t\).
Check: its weight is \(4+(-2)+3+1=6\), the computed label \(d(t)\). The labels also satisfy every edge inequality: \(4\le 0+4\), \(2\le 0+5\), \(2\le 4-2\), \(5\le 4+4\), \(5\le 2+3\), \(6\le 2+6\), and \(6\le 5+1\). Along any path from \(s\) to \(t\), adding the relevant inequalities shows that its cost is at least \(d(t)=6\). Since the displayed path attains 6, it is shortest.
For a finite shortest distance, predecessor pointers are a compact record of a path attaining the label. In a graph without reachable negative cycles, strict relaxation records a predecessor whenever it finds a better route. A negative cycle requires more caution: predecessor pointers in its region may keep changing, and they should not be read as a shortest path there.
Worked Example: A Negative Edge Changes the Best Route
Let \(V=\{s,a,b,c,t\}\), with directed edges in this scan order: \(s\to b\) (2), \(b\to c\) (2), \(c\to t\) (2), \(s\to a\) (5), \(a\to b\) (\(-4\)), \(a\to t\) (10). Start at \(s\). Initialize the labels as \((0,\infty,\infty,\infty,\infty)\) in the coordinate order \((s,a,b,c,t)\).
On pass 1, the first three edges give \(d(b)=2\), \(d(c)=2+2=4\), and \(d(t)=4+2=6\). The edge \(s\to a\) then gives \(d(a)=5\). The negative edge \(a\to b\) proposes \(5+(-4)=1<2\), changing \(d(b)\) to 1. Finally, \(a\to t\) proposes \(5+10=15\), which does not improve \(d(t)=6\). Thus the labels after pass 1 are \((0,5,1,4,6)\).
On pass 2, \(s\to b\) proposes 2 and does not improve 1. The edge \(b\to c\) proposes \(1+2=3<4\), so \(d(c)=3\). Then \(c\to t\) proposes \(3+2=5<6\), so \(d(t)=5\). The remaining edges do not improve any label: \(s\to a\) gives 5, \(a\to b\) gives \(5-4=1\), and \(a\to t\) gives 15. Passes 3 and 4 leave the labels unchanged at \((0,5,1,3,5)\).
The predecessor pointers give \(s,a,b,c,t\). Its weight is \(5+(-4)+2+2=5\). To check optimality directly, the final labels satisfy all six edge inequalities: \(1\le 0+2\), \(3\le 1+2\), \(5\le 3+2\), \(5\le 0+5\), \(1\le 5-4\), and \(5\le 5+10\). Adding the inequalities along any \(s\)-to-\(t\) path shows that its cost is at least 5; the reconstructed path has cost 5. The negative edge changes which route is best, but this graph has no directed cycle, and there is no unbounded decrease.
What the Extra Scan Detects
The next result explains the role of the extra scan. Here a distance is finite precisely when its vertex is reachable from the source. A vertex reachable from a reachable negative cycle has no finite shortest-path cost: paths to it can be made arbitrarily cheap by repeating the cycle before continuing.
Proof. First suppose there is no reachable negative cycle. Any directed walk from \(s\) can have a repeated-vertex portion removed without increasing its cost: that portion is a closed directed walk, and it is a union of directed cycles, each of nonnegative weight. Repeating this removal gives a simple path. A simple path has at most \(n-1\) edges.
After \(k\) full passes, every vertex with a path from \(s\) of at most \(k\) edges has a label no greater than the cost of that path. This follows by induction on \(k\). It holds at \(k=0\) for the length-zero path at \(s\). For the induction step, take a path of at most \(k\) edges and consider its last edge \(u\to v\). The prefix to \(u\) has at most \(k-1\) edges, so by the induction hypothesis \(d(u)\) is no greater than the prefix cost after pass \(k-1\). When \(u\to v\) is scanned in pass \(k\), relaxation makes \(d(v)\) no greater than the full path cost. Thus, after \(n-1\) passes, every reachable vertex has a label no greater than a shortest simple path cost. Labels cannot be less than the cost of every path that produced them, because each finite label is obtained from a path by relaxation. Therefore all reachable labels are shortest distances, and no further edge can improve one.
Now suppose a negative cycle is reachable. If the extra scan made no improvement, labels would remain unchanged throughout it. Every edge \(u\to v\) on the reachable cycle would then satisfy \(d(v)\le d(u)+w(u,v)\) at the end of the scan. Adding these inequalities around the cycle cancels all labels and gives \(0\le\) the total cycle weight, contradicting that the cycle is negative. So at least one relaxation improves. Unreachable cycles do not affect this argument: their vertices have label \(\infty\), and they cannot be reached by relaxation from \(s\). This proves both directions. \(\square\)
Worked Example: Detecting a Reachable Negative Cycle
Let \(V=\{s,a,b,c,t\}\), with edges scanned in this order: \(s\to a\) (0), \(a\to b\) (0), \(b\to c\) (\(-1\)), \(c\to a\) (0), \(c\to t\) (2). The directed cycle \(a\to b\to c\to a\) has weight \(0+(-1)+0=-1\), and it is reachable from \(s\). There are five vertices, so first perform four full passes.
Initialize \((d(s),d(a),d(b),d(c),d(t))=(0,\infty,\infty,\infty,\infty)\). Because updates apply immediately, the labels after the listed edges of pass 1 are: \(s\to a\) gives \(d(a)=0\); \(a\to b\) gives \(d(b)=0\); \(b\to c\) gives \(d(c)=-1\); \(c\to a\) gives \(d(a)=-1\); and \(c\to t\) gives \(d(t)=1\). The complete pass results are:
| Point in the trace | \(d(s)\) | \(d(a)\) | \(d(b)\) | \(d(c)\) | \(d(t)\) |
|---|---|---|---|---|---|
| Initialization | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| After pass 1 | 0 | -1 | 0 | -1 | 1 |
| After pass 2 | 0 | -2 | -1 | -2 | 0 |
| After pass 3 | 0 | -3 | -2 | -3 | -1 |
| After pass 4 | 0 | -4 | -3 | -4 | -2 |
Now scan once more, again in the same order. The edge \(s\to a\) proposes \(0+0=0\), which does not improve \(d(a)=-4\). The edge \(a\to b\) proposes \(-4+0=-4<-3\), so \(d(b)\) becomes \(-4\). Next, \(b\to c\) proposes \(-4+(-1)=-5<-4\), so \(d(c)\) becomes \(-5\). The edge \(c\to a\) proposes \(-5+0=-5<-4\), so \(d(a)\) becomes \(-5\). By the time \(c\to t\) is scanned, \(d(c)=-5\), so it proposes \(-5+2=-3<-2=d(t)\) and decreases \(d(t)\) to \(-3\). The improvement on \(a\to b\) already suffices to detect the reachable negative cycle.
Check: after one traversal of the cycle the cost decreases by 1, because its weight is \(-1\). Repeating it \(k\) times and then taking \(a\to b\to c\to t\) gives a path cost of \(-k+1\), which has no lower bound as \(k\) increases. Thus there is no finite shortest-path distance to \(t\), consistent with its label continuing to decrease.
Common Pitfalls and a Practical Checklist
Using stale labels during a scan. In the last example, a mistaken calculation might use the pass-4 value \(d(c)=-4\) when processing \(c\to t\) on the extra scan and conclude that the proposal is \(-4+2=-2\), equal to \(d(t)=-2\). That ignores the earlier extra-scan updates: \(a\to b\) first changes \(d(b)\) to \(-4\), and \(b\to c\) then changes \(d(c)\) to \(-5\). The correct proposal is \(-5+2=-3\), which improves \(d(t)=-2\). Use the current label at the moment each edge is scanned.
Confusing a negative edge with a negative cycle. In the first two examples, negative edges cause useful improvements, but do not by themselves mean that shortest paths fail to exist. The key obstruction is a negative cycle reachable from the source. A negative cycle in a disconnected part of the graph does not trigger this source-based test.
Reading a changing label as a final answer. If the extra scan finds an improvement, the labels on affected vertices are not final shortest distances. In particular, predecessor pointers may continue to change. If no reachable negative cycle exists, the \(n-1\) passes suffice; if one does exist, repeated traversals can make costs arbitrarily small for vertices reachable from it.
Check Your Understanding
For each question, specify the scan order if you perform a hand trace, and apply updates immediately.
- Why does the edge \(a\to b\) in the second worked example improve \(d(b)\), even though a route to \(b\) was found earlier in the same pass?
- In the negative-cycle example, what is the total weight of \(a\to b\to c\to a\), and why does that prevent a finite shortest-path distance to \(t\)?
- Suppose a graph has six vertices and no negative cycle reachable from \(s\). How many full passes does Bellman–Ford perform before its extra scan?
- Why can an unreachable negative cycle leave all source-based distance labels unchanged?
- In the last worked example, calculate the proposal for \(c\to t\) on the extra scan using the current value of \(d(c)\). Why is using its value from after pass 4 incorrect?