Why the Number of Edges Matters
Bellman–Ford can use negative edge weights, but its correctness is not based on permanently settling a vertex. Instead, its passes give a bound on how many edges of a path have been accounted for. This makes path length the natural parameter for the proof: a shortest path with \(k\) edges can be built by extending a path with at most \(k-1\) edges by one edge.
Throughout, \(G=(V,E)\) is a finite directed graph with a real weight \(w(u,v)\) on each directed edge \((u,v)\), and \(s\in V\) is the source. A directed walk is a sequence of vertices whose consecutive pairs are directed edges; its cost is the sum of their weights. A directed path has no repeated vertices. The walk of length zero at \(s\) has cost zero. A vertex is reachable from \(s\) if some directed path leads from \(s\) to it. We use \(\infty\) to indicate that no such path has been found.
A directed cycle is reachable from \(s\) if some vertex on it is reachable from \(s\). In this tutorial, “no reachable negative cycle” means that every directed cycle reachable from \(s\) has nonnegative total weight. This condition allows negative edges and even negative cycles in parts of the graph that cannot be reached from \(s\).
For the last statement, any repeated vertex in a walk identifies a closed segment. A closed walk can be split into directed cycles by repeatedly splitting at repeated vertices. If no reachable negative cycle exists, each such cycle has nonnegative cost. Removing the closed segments therefore does not increase the walk’s cost, and leaves a path with no more edges.
The Path-Length Recurrence
Initialize \(D_0(s)=0\) and \(D_0(v)=\infty\) for \(v\ne s\). To compute the next layer, allow either a walk that already used at most \(k-1\) edges, or one that ends with an edge \((u,v)\) after a walk to \(u\). Thus the recurrence is
If \(v\) has no incoming edges, the inner minimum is \(\infty\). An expression \(\infty+w(u,v)\) is interpreted as \(\infty\). This recurrence is implemented by a synchronous pass: every new value uses only the values from the previous layer.
Proof. We use induction on \(k\). For \(k=0\), the only walk allowed is the length-zero walk at \(s\). Its cost is zero; no other vertex can be reached with zero edges. These are exactly the initialized values.
Now let \(k\ge1\) and assume the claim holds for \(k-1\). Any walk to \(v\) using at most \(k\) edges either uses at most \(k-1\) edges, or has a last edge \((u,v)\). In the first case its cost is at least \(D_{k-1}(v)\). In the second case, the portion ending at \(u\) uses at most \(k-1\) edges, so its cost is at least \(D_{k-1}(u)\) by the induction hypothesis; adding the last edge gives cost at least \(D_{k-1}(u)+w(u,v)\). Hence every allowed walk has cost at least the recurrence’s value. Conversely, each finite candidate in the recurrence is realized by an allowed walk: use a walk achieving the previous-layer value, and, for an edge candidate, append \((u,v)\). The minimum of these candidates is therefore attained by an allowed walk. This proves the claim for \(k\), and completes the induction. \(\square\)
What an In-Place Pass Guarantees
The common implementation scans the edge list and updates one array in place: when \((u,v)\) is scanned, replace the current label of \(v\) by the smaller of its current value and the current label of \(u\) plus \(w(u,v)\), provided the label of \(u\) is finite. The scan order can allow information to travel across several edges during one pass. Consequently, after \(k\) in-place passes, a label need not equal the minimum among walks with at most \(k\) edges. The guarantee needed for correctness is that it is no greater than the cost of every path using at most \(k\) edges.
Proof. For \(k=0\), the only path using zero edges starts and ends at \(s\), and its cost is zero, equal to the initial label of \(s\). Assume the proposition holds after \(k\) passes. Consider a path \(P\) of at most \(k+1\) edges. If it has at most \(k\) edges, the induction hypothesis already gives the required inequality, and labels do not increase during a pass. Otherwise, write \(P\) as a path \(P'\) to \(u\), followed by an edge \((u,v)\). The path \(P'\) has \(k\) edges. At the start of pass \(k+1\), the label of \(u\) is at most the cost of \(P'\). Labels only decrease during the pass, so when \((u,v)\) is scanned, the label of \(u\) is still at most that cost. Relaxing \((u,v)\) makes the label of \(v\) at most the cost of \(P'\) plus \(w(u,v)\), which is the cost of \(P\). This proves the induction step. \(\square\)
Each finite label in the in-place algorithm is also the cost of some walk from \(s\): initially this holds for the length-zero walk, and a successful relaxation appends one edge to a walk witnessing the label of its tail. This fact, together with the path-length guarantee, gives correctness under the appropriate cycle condition.
Why \(n-1\) Passes Suffice
Proof. First consider a vertex \(v\) reachable from \(s\). Among walks from \(s\) to \(v\), repeated-vertex segments can be removed without increasing cost: each is a closed walk reachable from \(s\), and decomposes into cycles of nonnegative cost. Repeating this removal gives a path whose cost is no greater. Thus a shortest distance is attained by a path with no repeated vertices. Such a path uses at most \(n-1\) edges, since it has at most \(n\) distinct vertices.
By the proposition, after \(n-1\) passes the label of \(v\) is at most the cost of this shortest path, so it is at most the shortest-path distance. For the reverse inequality, every finite label is the cost of a walk from \(s\) to \(v\). Removing repeated-vertex segments from that walk gives a path of no greater cost. The shortest-path distance is therefore at most the walk’s cost, and hence at most the label. The two inequalities show that the label equals the shortest-path distance.
If \(v\) is unreachable, no relaxation can give it a finite label: a finite label would be witnessed by a walk from \(s\) to \(v\), contradicting unreachability. Finally, when \(n=1\), there are zero passes. The source has distance zero by the length-zero path, and there are no other vertices; the result holds in this case as well. \(\square\)
Worked Example: Synchronous Passes Track the Edge Bound
Consider the directed weighted graph with \(V=\{s,a,b,t\}\) and edges \((s,a)\) of weight \(4\), \((s,b)\) of weight \(5\), \((a,b)\) of weight \(-2\), \((a,t)\) of weight \(6\), and \((b,t)\) of weight \(3\). Use synchronous passes, so each new row is computed only from the preceding row.
At \(k=0\), the labels \((s,a,b,t)\) are \((0,\infty,\infty,\infty)\). With one edge, \(a\) can be reached at cost \(4\), and \(b\) at cost \(5\); \(t\) cannot yet be reached. The \(k=1\) row is \((0,4,5,\infty)\).
For \(k=2\), the candidate for \(b\) through \(a\) is \(4+(-2)=2\), so its label is \(\min(5,2)=2\). The candidates for \(t\) are \(4+6=10\) through \(a\) and \(5+3=8\) through \(b\), so its label is \(8\). The \(k=2\) row is \((0,4,2,8)\).
For \(k=3\), the candidate for \(t\) through \(b\) is \(2+3=5\), so its new label is \(\min(8,5)=5\). The other labels remain \(0,4,2\). The \(k=3\) row is \((0,4,2,5)\).
Check: The path \(s,a,b,t\) has cost \(4+(-2)+3=5\). The other paths to \(t\) are \(s,b,t\), with cost \(5+3=8\), and \(s,a,t\), with cost \(4+6=10\). Thus the label \(5\) is the shortest distance. This graph has no directed cycle, so the no-reachable-negative-cycle condition holds.
Worked Example: In-Place Relaxation Can Get Ahead
Let \(V=\{s,a,b,c\}\) and let the directed edges, scanned in this order, be \((s,a)\) of weight \(2\), \((a,b)\) of weight \(2\), and \((b,c)\) of weight \(2\). The graph has no cycles. Start with labels \((0,\infty,\infty,\infty)\).
In the first pass, scanning \((s,a)\) sets \(a=0+2=2\). Scanning \((a,b)\) then sets \(b=2+2=4\). Scanning \((b,c)\) sets \(c=4+2=6\). The labels after this one pass are \((0,2,4,6)\).
In the synchronous version, the first pass uses only the initial labels. It sets \(a=2\), while \(b\) and \(c\) stay at \(\infty\), because their tails had label \(\infty\) in the previous row. The synchronous labels are therefore \((0,2,\infty,\infty)\).
Check: The only path to \(c\) is \(s,a,b,c\), which uses three edges and costs \(2+2+2=6\). The in-place pass finds this path immediately because the edge order runs forward. It has found a valid path cost, but its label for \(c\) is not the minimum among paths using at most one edge—there is no such path. This is why the exact recurrence is stated for synchronous passes, while the in-place proof uses an upper bound on path costs.
Worked Example: Negative Edges and an Unreachable Negative Cycle
Let \(V=\{s,a,b,x,y\}\), with directed edges \((s,a)\) of weight \(2\), \((s,b)\) of weight \(4\), \((a,b)\) of weight \(-5\), \((b,a)\) of weight \(6\), \((x,y)\) of weight \(-2\), and \((y,x)\) of weight \(1\). Use synchronous passes. The cycle \(a,b,a\) has cost \(-5+6=1\); the cycle \(x,y,x\) has cost \(-2+1=-1\), but neither \(x\) nor \(y\) is reachable from \(s\).
The initial row for \((s,a,b,x,y)\) is \((0,\infty,\infty,\infty,\infty)\). After one pass it is \((0,2,4,\infty,\infty)\). After two passes, the candidate for \(b\) through \(a\) is \(2+(-5)=-3\), so the row is \((0,2,-3,\infty,\infty)\). After three passes, the candidate for \(a\) through \(b\) is \(-3+6=3\), which does not improve \(a=2\); the row remains \((0,2,-3,\infty,\infty)\). A fourth pass makes no further change.
Check: There are \(n=5\) vertices, so \(n-1=4\) passes suffice by the theorem. The shortest path to \(b\) is \(s,a,b\), with cost \(2+(-5)=-3\); the direct path to \(b\) costs \(4\). The shortest distance to \(a\) is \(2\), and \(x,y\) are unreachable, so their labels remain \(\infty\). The negative cycle is unreachable and does not affect these source distances.
Common Mistake and the Role of the Assumption
A common mistake is to say that an in-place pass computes exactly the best costs among paths with at most that many edges. The preceding four-vertex example disproves this: one pass gives \(c\) the finite label \(6\), even though no path to \(c\) uses at most one edge. The correction is to distinguish the two statements: synchronous passes compute the exact bounded-edge recurrence, while in-place passes are guaranteed to account for every path up to the pass number and may also propagate farther, depending on edge order.
The no-reachable-negative-cycle assumption is essential for finite shortest distances. If a negative cycle is reachable, a walk can travel to it, go around it repeatedly, and then continue to a destination. Each extra trip lowers the cost, so there need not be a minimum finite cost. Without that assumption, the \(n-1\)-pass path guarantee still applies to paths, but it does not establish that the resulting labels are shortest distances among all walks.
Check Your Understanding
For each question, distinguish carefully between a synchronous pass and an in-place pass.
- State the recurrence for \(D_k(v)\) and explain why the edge candidate uses \(D_{k-1}(u)\).
- In a graph with \(n=6\) vertices and no reachable negative cycle, what is the largest number of edges needed by a shortest path from the source to a reachable vertex?
- Give an example of why an in-place pass can produce a finite label for a vertex that has no path to it using at most one edge.
- Why can a negative cycle that is unreachable from the source be irrelevant to the source’s shortest distances?
- Explain why a finite label produced by relaxation is the cost of some walk from the source.