Why Bellman–Ford Needs an Extra Check
Bellman–Ford computes shortest-path distances even when some edge weights are negative. But a negative cycle reachable from the source changes the question: by traversing that cycle repeatedly, a walk can have weight as small as we wish. The usual \(|V|-1\) passes are followed by one more test to detect whether this has happened. The test is not meant to find a shorter finite distance; it detects that no finite shortest-walk distance exists for some vertices.
Throughout, \(G=(V,E)\) is a finite directed graph with a real weight \(w(u,v)\) on each edge \(u\to v\), and \(s\in V\) is the source. A directed walk may repeat vertices and edges. Its weight is the sum of the weights of its edges. A directed path has no repeated vertices, and a directed cycle is a closed directed walk with no repeated vertices other than its first and last vertex. The weight of a cycle is the sum of its edge weights; it is negative if that sum is less than \(0\).
If there is no negative cycle on any directed route from \(s\) to \(v\), a minimum walk weight exists: any repeated-vertex section of a walk is a closed walk, and if all directed cycles on such routes have nonnegative weight, removing that section does not increase the weight. Repeating this removal gives a path. There are finitely many paths, so a minimum is attained. In contrast, if a negative cycle is reachable from \(s\) and can reach \(v\), going around it repeatedly makes the weights of \(s\)-\(v\) walks unbounded below. A negative cycle elsewhere does not, by itself, have either effect on \(v\).
The Extra-Pass Test
Initialize labels by \(d[s]=0\) and \(d[v]=+\infty\) for \(v\ne s\). To relax an edge \(u\to v\), if \(d[u]\) is finite and \(d[u]+w(u,v)<d[v]\), replace \(d[v]\) by \(d[u]+w(u,v)\). A full pass scans every edge once. We use \(n=|V|\), run \(n-1\) full passes, and then test every edge once more. For the test, compare using the labels at the end of pass \(n-1\); the test may be treated as a snapshot, so updates made while scanning it do not affect other comparisons.
Proof. First, every finite label produced by relaxation is the weight of some directed walk from \(s\): this holds for the initial label \(d[s]=0\), and a relaxation appends the relaxed edge to a walk represented by \(d[u]\). Also, after \(k\) full passes, every \(s\)-\(v\) path of at most \(k\) edges has had its weight considered for \(d[v]\). For the induction step, the first \(k-1\) edges of such a path have been considered by the end of pass \(k-1\); in pass \(k\), scanning its last edge considers the whole path. Labels can only decrease, so the claim holds even if other updates occur during that pass.
Suppose first that no negative cycle is reachable from \(s\). Every reachable vertex then has a minimum walk weight, attained by a path: any repeated-vertex section would contain directed cycles, all of which have nonnegative weight, so removing the section cannot increase the walk weight. A path has at most \(n-1\) edges. By the preceding pass property, after \(n-1\) passes the label of each reachable vertex is at most its minimum walk weight. It is also at least that minimum, because every finite label is the weight of an actual walk. Hence each reachable label equals its distance. For every edge \(u\to v\) with finite \(d[u]\), appending that edge gives a walk to \(v\), so \(d[v]\le d[u]+w(u,v)\). No edge can pass the extra-pass test.
Conversely, suppose a negative cycle is reachable from \(s\). Each vertex on that cycle is reachable by a path of at most \(n-1\) edges, so each has a finite label after \(n-1\) passes. If no edge on the cycle passed the test, then for each of its edges \(u\to v\) we would have \(d[v]\le d[u]+w(u,v)\). Summing these inequalities around the cycle cancels all labels and gives \(0\le\) the weight of the cycle. That contradicts its negative weight. Therefore some edge passes the test. This proves both directions. \(\square\)
The proof also explains why the test concerns reachability: a cycle can be used in a walk from \(s\) only if it can be reached from \(s\). Unreachable vertices retain label \(+\infty\), so an edge within a disconnected negative cycle has no finite tail label and cannot trigger a relaxation.
Worked Tests
Worked Example: A Reachable Negative Cycle
Let \(V=\{s,a,b,t\}\), with directed weighted edges \(s\to a\) of weight \(1\), \(a\to b\) of weight \(1\), \(b\to a\) of weight \(-3\), and \(b\to t\) of weight \(2\). Scan edges in that order. There are \(n=4\) vertices, so run \(n-1=3\) full passes.
Initially the labels \((d[s],d[a],d[b],d[t])\) are \((0,+\infty,+\infty,+\infty)\). On pass 1, the edge \(s\to a\) gives \(0+1=1\), so \(d[a]=1\). Then \(a\to b\) gives \(1+1=2\), so \(d[b]=2\). Then \(b\to a\) gives \(2-3=-1<1\), so \(d[a]=-1\). Finally \(b\to t\) gives \(2+2=4\), so \(d[t]=4\). The labels are now \((0,-1,2,4)\).
On pass 2, \(s\to a\) proposes \(0+1=1\), which does not improve \(-1\). Edge \(a\to b\) proposes \(-1+1=0<2\), so \(d[b]=0\). Edge \(b\to a\) proposes \(0-3=-3<-1\), so \(d[a]=-3\). Edge \(b\to t\) proposes \(0+2=2<4\), so \(d[t]=2\). The labels are \((0,-3,0,2)\).
On pass 3, \(s\to a\) again proposes \(1\), which does not improve \(-3\). Edge \(a\to b\) proposes \(-3+1=-2<0\), so \(d[b]=-2\). Edge \(b\to a\) proposes \(-2-3=-5<-3\), so \(d[a]=-5\). Edge \(b\to t\) proposes \(-2+2=0<2\), so \(d[t]=0\). The labels after \(n-1\) passes are \((0,-5,-2,0)\).
On the extra-pass test, the edge \(a\to b\) proposes \(-5+1=-4\), and \(-4<-2\). Thus the test detects a reachable negative cycle. Indeed, \(a\to b\to a\) has weight \(1+(-3)=-2<0\). Vertex \(t\) is reachable from this cycle, so its walk weights are also unbounded below.
Check: another trip around the cycle changes a walk’s weight by \(-2\). After \(k\) trips, the weight of the walk from \(s\) to \(a\) that first uses \(s\to a\) is \(1-2k\), which has no finite lower bound as \(k\) increases.
Worked Example: An Unreachable Negative Cycle
Let \(V=\{s,a,b,x,y\}\), with directed weighted edges \(s\to a\) of weight \(4\), \(a\to b\) of weight \(3\), \(x\to y\) of weight \(-2\), and \(y\to x\) of weight \(1\). Scan them in that order. There are \(n=5\) vertices, so run four full passes.
Initially the labels \((d[s],d[a],d[b],d[x],d[y])\) are \((0,+\infty,+\infty,+\infty,+\infty)\). On pass 1, \(s\to a\) gives \(0+4=4\), and \(a\to b\) gives \(4+3=7\). The edge \(x\to y\) cannot relax because \(d[x]=+\infty\), and \(y\to x\) cannot relax because \(d[y]=+\infty\). The labels are \((0,4,7,+\infty,+\infty)\).
On pass 2, the two source-component proposals are \(0+4=4\) and \(4+3=7\), so neither label changes. Both cycle edges still have an unreachable tail, so the labels remain \((0,4,7,+\infty,+\infty)\). Passes 3 and 4 make exactly the same comparisons and leave the labels unchanged. On the extra-pass test, \(x\to y\) and \(y\to x\) still have infinite tail labels, so neither can trigger a relaxation.
Check: the disconnected cycle has weight \((-2)+1=-1<0\), but there is no directed walk from \(s\) to either \(x\) or \(y\). The distances from \(s\) to \(a\) and \(b\) are \(4\) and \(4+3=7\); neither can be changed by walks in a separate component.
Worked Example: Negative Edge, No Negative Cycle
Let \(V=\{s,a,b,t\}\), with directed weighted edges \(s\to a\) of weight \(2\), \(s\to b\) of weight \(5\), \(a\to b\) of weight \(-1\), \(b\to t\) of weight \(2\), and \(a\to t\) of weight \(5\). Scan them in this order. Here \(n-1=3\).
Initially the labels are \((0,+\infty,+\infty,+\infty)\). On pass 1, \(s\to a\) gives \(0+2=2\), and \(s\to b\) gives \(0+5=5\). Then \(a\to b\) gives \(2+(-1)=1<5\), so \(d[b]=1\). Edge \(b\to t\) gives \(1+2=3\), and \(a\to t\) proposes \(2+5=7\), which does not improve \(d[t]=3\). The labels are \((0,2,1,3)\).
On pass 2, the proposals for \(a,b,t\), in edge order, are \(2\), \(5\), \(1\), \(1+2=3\), and \(2+5=7\). Each is at least its current label, so the labels remain \((0,2,1,3)\). Pass 3 has the same proposals and leaves the labels unchanged. The extra-pass test also finds no improvement.
Check: the paths to \(a\) and \(b\) have minimum weights \(2\) and \(\min(5,2-1)=1\). The two paths to \(t\) have weights \(2-1+2=3\) and \(2+5=7\), while the path \(s\to b\to t\) has weight \(5+2=7\). Thus the minimum to \(t\) is \(3\), matching the final label. The negative edge alone does not imply a negative cycle.
Identifying Which Vertices Are Affected
The existence of a relaxable edge answers whether some negative cycle is reachable. To identify all vertices whose walk weights are unbounded below, use this precise version of the test: after the first \(n-1\) passes, record the head \(v\) of every edge \(u\to v\) satisfying \(d[u]<+\infty\) and \(d[u]+w(u,v)<d[v]\), using the same frozen labels for every comparison. Then follow directed edges forward from all recorded heads. The recorded heads and every vertex reachable from them have distance \(-\infty\).
To justify the claim, a negative cycle reachable from \(s\) must have a relaxable edge on the cycle by the theorem’s proof. The head of that edge can reach every vertex on the cycle, and every vertex reachable from the cycle can therefore be reached from a recorded head. Conversely, a recorded head has a walk from \(s\), and its label can still be improved after \(n-1\) passes. If no negative cycle could lie on a route from \(s\) to that head, a minimum walk to it would be a path of at most \(n-1\) edges, so its label would already equal the minimum and no improvement would be possible. Thus a negative cycle lies on a route to each recorded head. Every vertex reached forward from such a head can be reached after traversing that cycle, so repeated trips around the cycle make its walk weights unbounded below.
Common Pitfall
Do not treat every negative cycle in the graph as relevant. A tempting but incorrect argument is: “There is a negative cycle, so Bellman–Ford must report one.” In the second example, the cycle weight is \((-2)+1=-1\), but its vertices have labels \(+\infty\), and the extra-pass condition requires a finite tail label. The algorithm correctly leaves the source’s distances \(d[a]=4\) and \(d[b]=7\) unchanged. The right condition is a negative cycle reachable from the source; for a particular target’s distance to be \(-\infty\), the cycle must also be able to reach that target.
The extra pass is a test, not a further guarantee of finite shortest distances. Once it detects a reachable negative cycle, labels downstream of that cycle should not be reported as ordinary finite shortest-path distances: their walk weights are unbounded below.
Check Your Understanding
For each question, distinguish reachability from the mere presence of a negative cycle.
- Why can a negative cycle in a component unreachable from \(s\) not cause an edge to pass the extra-pass test?
- A graph has \(n=6\) vertices and no negative cycle reachable from \(s\). How many full passes are used before the test, and why can no edge then be relaxable?
- Suppose a negative cycle is reachable from \(s\), but there is no directed route from that cycle to \(v\). Is the distance to \(v\) necessarily \(-\infty\)? Explain.
- What inequality would the labels on a directed cycle satisfy if no edge of that cycle were relaxable? Why does that rule out a negative cycle?
- Why does one negative edge, without a reachable negative cycle, not prevent a finite shortest-walk distance?