1. Setting and conventions
Definition 16.1.1
(Walks and shortest distance)
Let be a finite directed graph with , , real weights , and source (so ). A walk may repeat vertices and edges. The walk with zero edges at is allowed and has weight .
The shortest distance is an infimum over walks:
with .
Computational conventions.
- We use a real-RAM model, where adding and comparing reals costs .
- is a sentinel. It satisfies for real and .
- Because weights are real, the expression never arises. The algorithm never stores ; that label is assigned afterwards by reachability.
- An edge list enumerates all edges in . A conventional adjacency-list traversal also scans the vertices and costs .
2. Bounded-length distances and the recurrence
Definition 16.1.2
(Bounded-length distance)
Define as the minimum weight of a walk from to with at most edges, or if no such walk exists. For fixed there are finitely many such walks, so the minimum exists.
Proposition 16.1.3
(Bounded-length recurrence)
The numbers satisfy and for , and for every :
Proof
(Two inequalities between d_i and the right-hand side)
Call the right-hand side . We prove the inequality in each direction.
- () A walk with at most edges also has at most edges. Also, a walk to with at most edges, followed by , is a walk to with at most edges. Every candidate in is therefore the weight of some walk counted by . If a term is , the inequality holds trivially.
- () Take an optimal walk for . If has at most edges, then . Otherwise has exactly edges, so its last edge is some . The prefix has edges, so . If no walk exists, both sides are .
Synchronous Bellman–Ford computes from using two arrays. Each round scans every edge and reads only the old array. Updating in place (the asynchronous variant) is also correct, but its intermediate values no longer equal exactly. That is why we analyze the synchronous version.
Concept lensStructural
Rounds as layers of an acyclic graph
Make copies of each vertex. Join to with weight for each edge, and to with weight . This layered graph has no cycles, and is the least weight of a path from to . A negative cycle in becomes an endless descent through the layers.
3. Finite distances after rounds
Call a cycle relevant to if it contains a vertex with and .
Lemma 16.1.4
(Finite distance after n−1 rounds)
If is reachable and no negative cycle is relevant to , then , and this value is finite.
Proof
(Deleting nonnegative closed subwalks)
Every vertex on an – walk is reachable from and reaches . Any closed subwalk of such a walk therefore decomposes into simple cycles that are relevant to . Each of those cycles has nonnegative weight, so . Deleting thus never increases the weight. Repeating this yields a simple path with at most edges and weight no larger than the original walk. Hence every walk weighs at least , so . The reverse inequality holds by definition.
Lemma 16.1.5
(A relevant negative cycle forces minus infinity)
If some negative cycle is relevant to , then .
Proof
(Going around the cycle repeatedly)
Walk from to a vertex on , go around times, then walk from to . The weight is , which tends to as .
Corollary 16.1.6
(Trichotomy of distances)
Together, the two lemmas give a trichotomy:
- exactly when is unreachable;
- exactly when a negative cycle is relevant to ;
- otherwise .
4. What the extra round proves
Compute one more round, , and let .
Proposition 16.1.7
(What the extra round certifies)
Let . (i) If , then a negative cycle reachable from exists. (ii) If a negative cycle reachable from exists, then every such cycle contains a vertex of . (iii) Every has .
Proof
(Proof of the three claims)
(i) a source-reachable negative cycle exists.
Suppose no reachable negative cycle exists. The finite-distance lemma then gives on reachable vertices. Since , round changes nothing. Unreachable vertices stay at .
(ii) A source-reachable negative cycle exists .
Let be such a cycle. Each is reachable, so is finite. Suppose for contradiction that for every . The recurrence gives
Summing around gives , a contradiction. In fact this shows more: every reachable negative cycle contains a vertex of .
(iii) .
If were finite, the proof of the finite-distance lemma would show that every – walk weighs at least . In particular , contradicting .
Proof X-ray
Why the sum around the cycle must close
The one non-obvious step is (ii). Assuming that no vertex of changes in round lets us read the recurrence, which is an inequality for , as an inequality between two values of the same array . Summing the inequalities around then cancels every label, leaving . This cancellation uses reachability: all labels are finite, so the subtractions are legitimate, whereas with labels nothing could be canceled. The argument is by contradiction over the whole cycle, so it proves only that some vertex of changes, not which one. Part (i) closes the other direction: if no reachable negative cycle exists, the finite-distance lemma already gives on reachable vertices, and round has nothing left to improve.
What the extra round does not say.
- A vertex in need not lie on a cycle.
- A vertex outside may still have , because it may simply not have improved in that particular round.
Counterexample mode
X is not the set of minus-infinity vertices
Claim: exactly when . Take vertices and edges (1), (), (1), (0), so . The cycle has weight . Listing , the recurrence gives and , so . Yet because lies on the cycle, and because is reachable from the cycle. The converse of (iii) is therefore false: records only the vertices that improved in this particular round. The correct statement is the theorem below, , which here equals .
Theorem 16.1.8
(Minus-infinity vertices are those reachable from X)
, the set of vertices reachable in from some vertex of , including itself.
Proof
(Two inclusions)
We show inclusion in each direction.
- () By (iii), every vertex of has . Moreover, and imply . So the label propagates along edges to all of .
- () If , the finite-distance lemma (contrapositive) gives a negative cycle relevant to , with . By (ii), contains some . Then reaches along , and reaches , so .
Final output. Run a BFS or DFS from and report:
- on ;
- where ;
- otherwise.
These cases are disjoint. Every vertex in is reachable, and so is every vertex reachable from .
Two distinctions.
- A negative cycle that is unreachable from has no effect on any distance, and the extra round cannot see it. Its vertices stay at .
- A vertex that is reachable from but not from any source-reachable negative cycle keeps the finite value .
Worked example 16.1.9
(Which vertices are minus infinity)
For example, take edges (weight 1), (weight 1), (weight ), (weight 1), plus a separate cycle with total weight . Then:
- ;
- ;
- .
5. Worked example
Worked example 16.1.10
(Five rounds on a graph with one negative edge)
The vertices are , with . The edges are:
| edge | |||||||
|---|---|---|---|---|---|---|---|
| weight | 1 | 3 | 3 | 1 | 5 | 2 |
There are two simple directed cycles: , of weight , and , of weight . Both are nonnegative, so there is no negative cycle.
| round | |||||
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 0 | 1 | 3 | ||
| 2 | 0 | 0 | 3 | 4 | 8 |
| 3 | 0 | 0 | 3 | 3 | 5 |
| 4 | 0 | 0 | 3 | 3 | 4 |
| 5 (extra) | 0 | 0 | 3 | 3 | 4 |
The table follows directly from the recurrence. Three entries are worth checking:
- In round 2, .
- In round 4, , which uses the four-edge path .
- In round 5, .
All rounds are genuinely needed. The extra round changes nothing, so , consistent with the absence of a negative cycle.
Worked example 16.1.11
(A single vertex with a self-loop)
Let with one self-loop of weight . Then , there are ordinary rounds, and . The extra round computes . If , then , so and : the loop is a nonnegative cycle. If , then , so and , since trips around the loop weigh . Even the smallest graph needs the extra round to expose its negative cycle.
Counterexample mode
Finalizing a vertex too early
Claim: since the graph above has no negative cycle, textbook Dijkstra computes its distances correctly.
Dijkstra's correctness argument needs nonnegative weights. Under that assumption, a path that leaves the finalized set can never become cheaper later. Here is what textbook Dijkstra does on this graph, where a vertex is finalized when it is extracted:
- Extract . Set and .
- Extract at 1 and finalize it. Set .
- Extract at 3. The edge would lower to , but is already finalized. Set .
- Extract at 4. Set .
- Extract .
The output is , , . The true values are , , and .
A variant that does lower to but never re-scans 's outgoing edges still leaves . The negative edge breaks the invariant on which the algorithm relies.
The repair is to keep Dijkstra for nonnegative weights only, and to use the bounded-length rounds above, which finalize nothing before round , when negative edges are present.
6. Complexity
Proposition 16.1.12
(Cost of Bellman–Ford with the extra round)
Synchronous Bellman–Ford with the extra round and the final search from runs in time and space.
Proof
(Counting rounds, edges and storage)
- Rounds. The algorithm runs rounds: ordinary rounds plus the extra one.
- Cost per round. Each round scans edges and copies an array of length , which is . The total is .
- The usual bound. First find the source-reachable subgraph in time; write for its numbers of vertices and edges. If , then , so the rounds take . Including the initial search gives . If , the rounds take instead, including the empty-edge case and possible self-loops.
- Reachability from . This costs .
- Space. covers the graph, two distance arrays, and the search.
Representation caveat. Direct edge enumeration costs , in addition to the array initialization or copy. With conventional adjacency lists, scanning vertices and their edges is also per round. If the graph is given as an adjacency matrix, scanning it costs per round and over rounds.
7. Common mistakes
Common mistake
(Reading as the answer when a negative cycle exists)
The vertex in the counterexample above has , a perfectly finite value, but . The values are distances only for vertices with no relevant negative cycle, which is exactly what the extra round and the search from are for.
Common mistake
(Counting a negative cycle that the source cannot reach)
A negative cycle with no walk from to it does not change any , and every one of its vertices keeps label in all rounds. Reporting "a negative cycle exists" for the whole graph is a different question from the one this algorithm answers, which concerns walks from .
Common mistake
(A finite sentinel for infinity)
If is stored as a large finite number , then relaxing an edge of weight out of an unreached vertex produces , which looks like an improvement over . Unreached vertices then appear in or acquire fake finite labels. Test that is finite before using it, or use a true infinity with .
8. Exercises
Quick check
(In the graph of the five-round example, can be read off after only rounds? Give and .)
Look at how many edges the best path to uses.
Solution · Answer
No. The table gives , but , achieved by the four-edge path and first visible in . A shortest path using edges needs rounds.
Quick check
(Vertices (so ) with edges (2), (), (1), (4). Find and every .)
Compute and , then use .
Solution · Answer
The cycle has weight . The rounds give and for , so . Then , so , while . Note that and are minus-infinity vertices outside .
Quick check
(A graph has a negative cycle that the source cannot reach. What are on that cycle and the set contributed by it?)
Which labels can ever become finite?
Solution · Answer
Every vertex of the cycle has , because there is no walk from to it. Its labels stay in every round, so none of its vertices belongs to . The negative cycle is invisible to the algorithm, correctly.
Exercise 16.1.13
(Show that if on every vertex, then for all .)
CoreProof
Solution(3)
- 1
Write the recurrence as a map
Let send an array to the array . Then for every .
- 2
Induct on k
Key step
For the claim is trivial, and is the hypothesis. If for some , then .
Because: Each array is determined by the previous one alone.
- 3
Conclude
∎Hence for all , and no further round can change any label.