A route planner may use a negative arc to represent a credit or a rebate. The difficulty is that a cycle with negative total length can be traveled repeatedly: if we may then reach the destination, there is no least-cost walk at all. Bellman–Ford separates this situation from an ordinary finite shortest route and from a destination that cannot be reached.
Walks, distances and the recurrence
Definition 24.1.1
(Walks and edge-limited distances)
Let be a finite directed graph with , source , and finite real arc lengths . A walk may repeat vertices and arcs; a path has no repeated vertices. The length of a walk is the sum of its arc lengths, including repetitions. Define as the minimum length of an -to- walk with at most arcs; it is if none exists. Write for the infimum of lengths of all -to- walks, with when there are none; it can also be .
The empty walk has length zero, so and for .
Proposition 24.1.2
(Edge-limited recurrence)
For , with and the inner minimum over no incoming arcs equal to ,
Proof
(Split by whether the last arc is used)
An admissible walk either uses at most arcs, or uses exactly and ends in some arc . In the latter case its prefix has at most arcs and length at least . Conversely, an attaining finite prefix followed by is an admissible walk. There are only finitely many walks with at most arcs in a finite graph, so every finite minimum used here is attained. Taking the minimum over the two possibilities proves the formula.
Computing each row from the previous row gives the literal edge-count interpretation. An in-place implementation can propagate along several arcs in one pass; it is valid for the usual algorithm, but its intermediate rows need not equal these values.
Concept lensAlgebraic
Bellman–Ford as matrix powers in min-plus arithmetic
Let be the least length of an arc from to , or if there is none, and then replace each diagonal entry by its minimum with . In the arithmetic where "sum" means and "product" means , define . The recurrence says exactly , so , and the entry of is the least length of a -to- walk with at most arcs.
Common mistake
(Reading an in-place pass as the row )
In the table example below, one in-place pass over the arcs in the listed order sets , , then through , , then through , and through . After that single pass already holds , although : no walk of one arc reaches . The final labels are still correct, but statements about “walks with at most arcs” hold only for synchronous rows.
Classifying destinations
After computing , mark the head of every arc satisfying , where the tail label is finite. Then mark every vertex reachable from any marked head.
Theorem 24.1.3
(Exact three-way classification)
A marked vertex has distance . An unmarked vertex whose label is is unreachable. Every other vertex has finite distance , attained by a simple path. Thus a reachable negative cycle affects a target only when the cycle can also reach that target.
Proof
(Improvement exposes a negative cycle, and a negative cycle forces improvement)
If an arc can improve its head after stages, append it to an attaining walk for its finite tail label. The resulting walk is strictly shorter than at its head and has at most arcs. It must contain a repeated vertex; moreover at least one cycle removed in decomposing this walk is negative. Otherwise all cycles could be removed without increasing its length, yielding a walk with at most arcs, a contradiction. That negative cycle is reachable from and can reach the marked head, hence every descendant of the head. Repeating it makes the walk length tend to .
Conversely, take any reachable negative cycle. Every vertex on it has a finite label, since a reachable vertex has a simple route from of at most arcs. If none of its arcs were improving, adding the inequalities around the cycle would imply its negative total length. At least one cycle vertex is therefore marked, and propagation marks every vertex reachable from that cycle. If a reachable target is not marked, no negative cycle on an -to-target walk can exist. Removing its nonnegative cycles yields a simple path no longer than the walk; the shortest simple path therefore attains the infimum and uses at most arcs. Finally, a reachable vertex always has such a simple route, so an infinite label means unreachable.
Proof X-ray
Why marking is both necessary and sufficient
The proof makes three separate claims. An improvement after stages yields a walk of at most arcs, so a vertex repeats, and the cycle decomposition must contain a negative cycle. A reachable negative cycle yields an improvement, by a telescoping sum. An unmarked reachable target has a finite distance attained by a simple path.
Key move: if no arc of a cycle improves, the labels satisfy on that cycle, which is a potential, and a potential cannot coexist with a negative cycle. Reachability is used exactly here, to make those labels finite so the sum makes sense.
What would break: with a non-strict test, a zero-length cycle would be reported (practice item 4). Without the propagation step, a vertex on the cycle can be missed: in the second table example the arc gives , equal to , so is never an improving head, yet .
How it closes: the bound on stages is exactly the number of arcs of a simple path, so once negative cycles are excluded nothing shorter can appear later.
The argument also handles : the initial row is , and a negative self-loop is detected by the extra scan. Zero-length cycles do not make an infimum and do not trigger a strict improvement merely because they can be repeated.
A complete table
Worked example 24.1.4
(A negative edge without a negative cycle)
Use arcs , , , , , , , and . Their only directed cycle is , of length . The synchronous rows are:
| Maximum arcs | |||||
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 0 | 4 | 5 | ||
| 2 | 0 | 4 | 2 | 8 | 9 |
| 3 | 0 | 4 | 2 | 5 | 6 |
| 4 | 0 | 4 | 2 | 5 | 6 |
For instance, row 2 gives , and row 3 gives . No arc improves row 4. The path has length ; also has length 6. Both attain the certified distance. The negative edge causes no problem for Bellman–Ford, while Dijkstra's standard proof requires nonnegative arc lengths.
Worked example 24.1.5
(A negative cycle and the marking step)
Now change only from to . The cycle has length . Rows to are unchanged. Row 3 gives , and . Row 4 gives , and , with still .
The extra scan finds two improving arcs: gives and gives . So and are marked heads. Propagation from marks through . Hence . Repeating the cycle does not let us travel backwards to or ; their distances remain 4 and 0, and neither is marked because no arc leaves the cycle toward them.
Worked example 24.1.6
(An unreachable component with a negative cycle)
Take vertices with arcs , and , so . The cycle has length , but no arc enters from . Every row from on is for .
In the extra scan the cycle arcs have tail label , so they are excluded and nothing is marked. The theorem then classifies as finite with distance , and as unreachable. The negative cycle exists but is irrelevant to every distance from ; the finiteness condition on the tail label is what keeps it from being reported.
Counterexample mode
A negative arc is not a negative cycle
A plausible claim is that a negative arc makes a distance unbounded. With only the arc of length , and . The extra scan compares with ; there is no strict improvement, nothing is marked, and the finite distance is . A single negative edge cannot be repeated. Conversely, a reachable negative cycle that cannot reach does not make the distance to unbounded below, as practice item 2 shows. The hypothesis in the classification is a reachable negative cycle that also reaches the target.
Common mistake
(Marking only the improving heads)
The extra scan finds only the heads of improving arcs. Vertices on or after the cycle can have distance without being such a head, as in the second table example shows. Always propagate the marks along all arcs before reporting finite distances.
Reconstructing a route and computational cost
For a finite unmarked target, store, for each synchronous state , whether its value was inherited or obtained from an incoming arc. Starting from , follow these choices backwards while decreasing ; reverse the recorded arcs to obtain an attaining walk. Remove any repeated-vertex cycles: for an unmarked target they have nonnegative total length, and removing a positive one would contradict optimality, so an optimal simple path remains. Ties can be resolved arbitrarily. A single predecessor per vertex without careful update rules is not the same as this stage-indexed record.
With adjacency lists, initialization and the complete synchronous scans take time as stated, including copying rows; marking and graph reachability take . Two rows use distance storage, while the straightforward stage-indexed route record uses state choices. These are arithmetic-operation bounds; actual bit complexity depends on how lengths are represented. A further relaxation signals a reachable negative cycle, not necessarily one relevant to every destination.
Practice
Quick check
(For , , , compute the shortest distance and explain why no negative cycle is present.)
Solution · Answer
The route through has length , less than the direct route's 0, so the answer is . All arcs advance from through or to ; there is no directed cycle.
Quick check
(Suppose , , and , with no other arcs. Classify .)
Solution · Answer
The source has distance 0, has distance by repeated self-loops, and has distance 3. The cycle cannot reach .
Quick check
(With and arcs , , , compute and and identify an improving arc in the extra scan.)
Solution · Answer
The synchronous rows give , and , . Arc gives and marks ; propagation marks as well.
Quick check
(Why does replacing strict improvement by non-strict comparison falsely identify a zero cycle? Give an example.)
Solution · Answer
A single zero-length self-loop at the source gives . It is an equality but not an improvement; every walk has length zero and the distance is finite.