A shorter route may arrive through a negative edge
Suppose an edge weight records a change in cost, including a credit or a refund. A negative edge can be meaningful. It also changes what a shortest-path algorithm must prove. A route that currently looks expensive can later use a negative edge to improve a vertex whose current distance looks settled. The greedy finalization used by Dijkstra's algorithm then loses its justification.
Bellman–Ford uses a different source of progress: allow a route to use more edges, and repeatedly improve distance estimates by extending known routes by one edge. The important questions are why finitely many rounds suffice when an optimum exists, and what an extra possible improvement tells us when they do not.
This note develops a shortest-path algorithm from dynamic programming and invariant-based analysis. We will distinguish the recurrence, whose rounds are easy to interpret, from an in-place implementation whose individual rounds may propagate several edges.
State the graph problem and its exceptional cases
Let be a finite directed graph with , a source , and a real weight on each edge. Parallel edges can be kept as separate edge records; a self-loop is also allowed. Arithmetic and comparisons in the mathematical analysis are exact.
A walk is a sequence of directed edges with matching endpoints. It may repeat vertices or edges. Its weight is the sum of its edge weights. The empty walk from to itself has weight zero. A simple path has no repeated vertex and consequently has at most edges.
Definition 7.1.1
(Shortest-walk distance)
For , let be the infimum of the weights of all -to- walks. It has three possible forms:
- : is unreachable from ;
- a finite minimum: an optimal walk exists;
- : weights of walks to can be made arbitrarily small.
A negative cycle is a directed cycle whose total edge weight is negative. If such a cycle is reachable from and can reach , repeating it before continuing to proves .
The reachability conditions matter. A negative cycle in a separate part of the graph does not affect routes from . Even a reachable negative cycle does not make every vertex's distance : it affects only vertices reachable from that cycle. The algorithm below reports whether some negative cycle is reachable from . It does not by itself classify every vertex with distance .
Put an edge budget on a walk
For an integer , define to be the minimum weight of a walk from to using at most edges. Use if there is none. There are finitely many such walks for a fixed finite , so a finite minimum exists even when the graph has a negative cycle.
Initially,
A walk using at most edges either already uses at most , or has a last edge preceded by at most edges. This gives
Ignore a candidate whose preceding value is . If there are no incoming edge candidates, the inner minimum is . Keeping the first term is essential: the budget is “at most”, not “exactly”.
Proposition 7.1.2
(Bounded-edge recurrence)
For every and every , the quantity defined above satisfies the recurrence, where the right-hand side is evaluated from row alone.
Proof
(Last-edge decomposition)
Let be the right-hand side. A walk with at most edges either has at most edges, so its weight is at least , or ends in some edge after an initial part with at most edges. That initial part weighs at least , so the whole walk weighs at least the candidate . Thus , and if no admissible walk exists.
Conversely, every finite term of is the weight of an admissible walk: is attained by a walk with at most edges, and a finite candidate is attained by an optimal walk to with at most edges followed by . Hence , the two are equal, and induction on from the stated row proves the whole table correct.
A worked table shows why several rounds are needed
Use vertices and the following edges. There are no other edges.
| Edge | Weight | Edge | Weight |
|---|---|---|---|
Worked example 7.1.3
(The best route to t uses four edges)
Compute every row solely from the previous row:
| Edge budget | |||||
|---|---|---|---|---|---|
For example, . At budget two, the improved value 2 is not yet available when extending a route from , since every entry must use row one. Thus . Budget three then gives and . Budget four finally gives , attained by
Using a newly written entry within the same row would describe an in-place scan, not this bounded-edge table. It might still produce a correct algorithm, but the row would lose its stated exact meaning.
Why n − 1 rounds suffice without a reachable negative cycle
Theorem 7.1.4
(Enough edges when no negative cycle is reachable)
If no negative cycle is reachable from , then for every .
Proof
(Shortcutting repeated vertices)
Assume no negative cycle is reachable from . If a walk from repeats a vertex, the section between two occurrences is a closed walk. It decomposes into directed cycles; each has nonnegative weight under the assumption. Removing that section therefore does not increase the walk's weight. Repeat until no vertex repeats.
Consequently, for every reachable an optimal simple path exists. There are only finitely many simple paths, and each has at most edges. Thus
for every , including unreachable vertices where both values are . For , the empty path remains optimal with value zero. This reasoning does not require each edge to be nonnegative. It requires the absence of a reachable negative cycle.
Relax edges in place, with a carefully chosen invariant
An edge relaxation tries the candidate d[u] + w(u,v) and replaces
d[v] only when the candidate is smaller. The ordinary implementation
stores one distance array and scans all edges repeatedly.
BELLMAN_FORD(V, E, s):
d[v] = INFINITY for every vertex v
d[s] = 0
repeat n - 1 times:
changed = false
for each edge (u, v, weight) in E:
if d[u] is not INFINITY and d[u] + weight < d[v]:
d[v] = d[u] + weight
changed = true
if not changed:
return (d, no reachable negative cycle)
for each edge (u, v, weight) in E:
if d[u] is not INFINITY and d[u] + weight < d[v]:
return (no distance answer, reachable negative cycle)
return (d, no reachable negative cycle)
INFINITY denotes a separate unreachable state, not an ordinary largest
integer to which a weight may safely be added. An implementation with
fixed-width integers must guard that state and ensure that every computed
finite sum fits its chosen type. Exact arithmetic is part of the present
proof; floating-point rounding can change a strict comparison.
Unlike the table, an in-place scan may immediately use a newly improved value. On a path scanned in forward order, one round can propagate all the way to its end. We do not claim that its labels equal the corresponding row.
Theorem 7.1.5
(Exactness of the in-place algorithm)
If no negative cycle is reachable from , the labels d[v] held when the algorithm returns, after scans or after an earlier scan that changes nothing, equal for every , with for unreachable .
Proof
(Two inequalities prove the in-place algorithm)
First, every finite label d[v] is the weight of some actual walk from
to . This is true of the initial zero label and is preserved by
extending the walk witnessing d[u] along the relaxed edge. Hence, when
there is no reachable negative cycle, .
Second, after complete edge scans, . It holds before
any scan. During the next scan, labels only decrease, so when edge
is processed, the current d[u] is no larger than its value at the start
of that scan, which by induction is at most . After all edges,
each last-edge candidate and the previous label have been considered.
The recurrence therefore gives .
After scans and without a reachable negative cycle,
so the labels are exact. Unreachable vertices cannot acquire finite labels because every finite label has a witnessing walk. The second inequality remains useful even when negative cycles exist; it is the first finite-optimum interpretation that then needs care.
Proof X-ray
A sandwich between two different facts
The proof is a sandwich, and its two sides use different facts. The lower bound comes only from the witnessing walks and needs no hypothesis on cycles. The upper bound comes from labels only decreasing, which is why an in-place scan does at least as well as the table without reproducing it row by row. The two sides meet through the earlier equality , and that is exactly where the absence of a reachable negative cycle enters.
The non-obvious move is to compare with the table rather than analyze the scan order, so the order of the edges never matters. Without the hypothesis the sandwich opens: can be while is a finite number, and the labels cannot be certified. The detection scan below handles that case.
If a whole scan changes no entry, every relaxation inequality already holds. A later scan starting from the same labels would do exactly the same work and also change nothing. Early stopping therefore preserves the result of the remaining scans. It cannot hide a reachable negative cycle, as the next argument shows.
Worked example 7.1.6
(An in-place run that stops early)
Run the algorithm on the five-vertex graph, scanning the edges in the order of the table: , , , , , , , . Start with for .
In the first scan, sets and sets . Then gives , so . Next sets , while offers , which is not smaller. Then sets , while offers and offers . After one scan , which already equals the row .
In the second scan every candidate is at least the current label: offers , offers , and offers . Nothing changes, so the algorithm returns after two of the at most scans. The first scan carried the improvement across four edges because the edge order followed the path, which one row of the bounded-edge table cannot do.
An extra improvement detects a reachable negative cycle
After scans, inspect every edge once more, without changing the
labels. If a finite d[u] can still improve d[v], report a reachable
negative cycle. Do not return those current numbers as shortest distances.
Theorem 7.1.7
(Negative-cycle detection)
Suppose the main loop has ended, either after scans or at a scan that changed nothing. Then some edge with finite d[u] satisfies if and only if a negative cycle is reachable from . In particular, an unchanged scan never occurs when a reachable negative cycle exists.
Proof
(Exact labels against a cycle sum)
If no negative cycle is reachable, the preceding theorem makes every label exact. Extending an optimal walk to along gives a feasible walk to , so . No edge can strictly improve its endpoint, so a reported improvement implies that the assumption was false.
Conversely, suppose a negative cycle is reachable. Every vertex on it is reachable by some simple path from , hence has a finite label after scans. If none of its edges were relaxable, each cycle edge would satisfy . Adding these inequalities around the cycle cancels every distance label and yields , contradicting negativity. At least one such edge must therefore be relaxable.
The same sum rules out an unchanged full scan in the presence of a reachable negative cycle: unchanged relaxation inequalities propagate finite reachability from along every path, and then contradict the cycle.
Proof X-ray
Two directions with different engines
The directions are not symmetric. The direction "no cycle, so no improvement" rests on the exactness of the labels, hence on the whole earlier theorem; it adds only the observation that extending a walk gives a walk. The direction "cycle, so some improvement" uses nothing about the algorithm except that the labels on the cycle are finite.
Its key move is a cancellation: if every edge of a cycle satisfied its relaxation inequality, summing around the cycle would make each label appear once with each sign, leaving . A condition that holds edge by edge cannot survive a negative total. The finiteness comes from simple paths of at most edges, which is why scans suffice. If the cycle were unreachable, its labels would stay , the finite guard would skip its edges, and the sum could not be formed; this is why unreachable negative cycles are not reported.
Worked example 7.1.8
(A cycle affects some distances, not all of them)
Add of weight to the five-vertex graph. The cycle has weight . It is reachable from , and its vertices can reach . Thus have distance . The source still has distance zero, because no edge leads back to . The detection test reports the reachable negative cycle; it does not replace every entry by .
Instead, leave the original graph unchanged and add a separate component with edges of weight and of weight . This cycle is negative but unreachable from . Both labels remain , so the finite-predecessor guard excludes these edge candidates. Distances in the original component remain those in the worked table.
A negative edge invalidates Dijkstra's greedy proof
Counterexample mode
A finalized distance can later need improvement
Take vertices and only the edges of weight , of weight , of weight , of weight , and of weight .
A Dijkstra implementation that permanently finalizes the smallest tentative label first finalizes at 2, then at 4, before it processes at 5. But has weight . There is no directed cycle at all. The problem is therefore the negative edge, rather than a negative cycle. Allowing settled vertices to reopen changes the algorithm; the usual Dijkstra correctness and running-time argument no longer applies.
Running time and what the returned result promises
Proposition 7.1.9
(Cost of the algorithm)
Write . The algorithm runs in worst-case time and uses auxiliary distance storage, apart from the input graph.
Proof
(Counting edge examinations)
Initialization costs . At most main scans and one detection scan each examine edge records at constant cost, which is in total. The distance array has entries.
For graphs with at least one edge this is often written , but the initialization still matters when . Keeping every bounded-edge table row instead would use distance storage; the in-place algorithm does not need that table.
The implementation returns either correct source distances, or a warning that some reachable negative cycle exists. A cycle witness, reconstructed shortest paths, and a list of all vertices with distance are additional outputs requiring additional bookkeeping. In particular, to classify affected vertices, one can start from endpoints of relaxable edges after the main scans and traverse all vertices reachable from them; this is a separate classification step, not a property of every current finite label.
Common mistakes
Common mistake
(Replacing “at most” by “exactly”)
Define as the minimum over walks with exactly edges, and the recurrence loses its first term. With the single edge of weight , , since no walk with exactly two edges exists, although . The budget “at most ” keeps shorter walks available.
Common mistake
(Using a large integer as INFINITY)
Suppose unreachable vertices carry , and an edge of weight joins two unreachable vertices. The test succeeds and gives a bogus finite label. If has weight , the labels then keep changing. The finite-predecessor guard in the pseudocode exists to prevent this.
Common mistake
(Returning the labels after a failed detection test)
Take edges of weight , of weight and of weight , scanned in that order, with . After two scans for , and a third scan would give for both. The detection test finds relaxable. These finite labels are not distances: the true values are , and the algorithm must report the cycle instead.
Solved exercises
Quick check
(Compute a bounded-edge table without using the new row)
Use vertices and edges of weight , of weight , of weight , and of weight . Find the rows in vertex order and give an optimal route to .
Solution · Answer
The rows are , and . At budget two, the improved value of cannot yet be extended to ; the value 6 comes from the preceding row's value 4. At budget three, gives . There are no cycles, and three is , so the last row contains the true distances.
Quick check
(Edge order changes propagation within a scan)
On the path with all three edge weights equal to 1, start from the initial distance array. Compare one in-place scan in forward edge order with one in reverse edge order. Does either outcome contradict the bounded-edge recurrence?
Solution · Answer
Forward order produces labels in vertex order , because each new value is immediately reused. Reverse order first meets two edges whose tails are unreachable, which are skipped, and only then processes , giving , which happens to equal . Neither outcome contradicts the recurrence: the in-place proof requires only after one scan and an actual walk witnessing each finite label. The forward result is smaller than at and , which is allowed; here it equals .
Quick check
(Reachability determines which negative cycle matters)
The only edges are of weight 2, of weight , of weight 1, of weight 7, of weight and of weight 1. Which vertices have distance , finite distance or from ? What does Bellman–Ford report?
Solution · Answer
The reachable cycle has weight , so and have distance . They cannot reach or , whose distances are 0 and 7. Vertices are unreachable and have distance , even though their own component also contains a negative cycle. Bellman–Ford reports a reachable negative cycle because of ; its basic warning does not itself provide this full classification.
Quick check
(A negative self-loop and a zero-weight cycle)
If and the only vertex is , how many main scans occur? What happens with a self-loop of weight ? What changes if its weight is 0?
Solution · Answer
There are main scans, but the detection scan still occurs. With weight , it compares and correctly reports a reachable negative cycle; the distance from to itself is . With weight 0 there is no strict improvement, and the distance is 0. A zero-weight cycle permits infinitely many equal-weight walks but does not make their weights unbounded below.