What a distance means
A road network can contain a negative edge cost, for example a credit applied on a transition. A greedy shortest-path argument that assumes nonnegative weights may then fail. We will instead build the best walk using a bounded number of edges, and separately detect when repeating a reachable negative cycle makes a finite minimum impossible.
Definition 4.2.1
(Walk distance and negative cycles)
Let be a finite directed graph with vertices, edges, a finite real weight for each edge , and source . Parallel edges, possibly of different weights, and self-loops are allowed. A walk may repeat vertices and edges. The empty walk from to itself has weight zero. For each vertex, the distance is the infimum of weights of all source-to-vertex walks; use if none exists. A negative cycle is a directed cycle (a closed walk that repeats no vertex except its endpoints; a self-loop counts) of negative total weight.
A vertex reachable from a source-reachable negative cycle has distance : go around the cycle arbitrarily many times before continuing to it. This does not mean a finite walk has weight .
Counterexample mode
Finalizing the nearest vertex fails with a negative edge
Take edges of weight , of weight and of weight . A nonnegative-weight greedy rule finalizes the nearest vertex at distance , because every other walk seems to start with something at least as long. But the walk has weight , so the true distance to is , and the finalized value was wrong. The argument "a later edge cannot shorten an earlier finalized vertex" needs nonnegative weights. The edge-count recurrence below avoids finalizing any vertex early: here in order and .
Dynamic programming by edge count
Definition 4.2.2
(Edge-bounded distance)
Let be the minimum weight of a walk from to using at most edges, or when there is none. Initialize and for .
Proposition 4.2.3
(Edge-count recurrence)
For ,
An empty inner minimum is , and plus a finite weight remains .
Proof
(Split a walk at its last edge)
A walk from to of at most edges either has at most edges, which contributes , or it has exactly edges and a last edge . In that case the part before is a walk from to of at most edges, so its weight is at least , and the whole walk weighs at least . Hence the right-hand side is a lower bound for every candidate. Conversely, appending any edge to a walk of at most edges that attains gives a valid walk of at most edges, so each term on the right is achieved by a real walk. There are finitely many walks of bounded length in a finite graph, so each finite minimum is attained. Induction on , starting from the base row , proves that the recurrence computes every exactly.
Use separate previous and next arrays: copy the previous array, then examine every edge using only previous-array values. This makes the meaning independent of edge order.
Proposition 4.2.4
(Finite distances after passes)
If no negative cycle reachable from can reach , then the distance to equals , which is finite when is reachable and otherwise.
Proof
(Removing nonnegative cycles leaves a simple path)
Every cycle on an – walk has nonnegative weight under the hypothesis. Removing a cycle from a walk cannot increase its weight, and repeating the removal leaves a simple path of at most edges. So the infimum over all walks equals the minimum over walks of at most edges, which is , and it is attained. An unreachable has no walk and stays at . The condition is local to : a negative cycle elsewhere does not make every distance unbounded.
Detecting and propagating negative cycles
Theorem 4.2.5
(The extra pass and affected vertices)
Compute and one more synchronous pass . A reachable negative cycle exists exactly when for at least one vertex. Let be all such vertices. The vertices reachable from are exactly those with distance .
Proof
(Improvement forces a cycle, and a cycle forces an improvement)
For one direction, if , a minimum walk witnessing the improvement uses edges and repeats a vertex. If every cycle on that walk had nonnegative weight, removing one would give a walk of at most edges with no greater weight, a contradiction. Thus a reachable negative cycle can reach .
Conversely, every vertex of a reachable cycle has some simple source path of at most edges and hence a finite . If no vertex of a reachable negative cycle improved in the extra pass, then for every cycle edge the recurrence would give . Summing around the cycle would force its total weight to be nonnegative, a contradiction. Therefore at least one vertex on every reachable negative cycle belongs to . A graph traversal from all vertices in marks precisely the vertices reachable after such a cycle. Unreachable negative cycles cause no improvement because their predecessor values remain .
Proof X-ray
Where the extra pass proof turns
The non-obvious move is the telescoping around the cycle. No improvement says that along every cycle edge the inequality already holds; adding these inequalities cancels every value and leaves . The cancellation is legitimate only because every value on a reachable cycle is finite, which is why the proof first records a finite for each of its vertices. On an unreachable cycle the values are , the inequality carries no information, and indeed no negative cycle there is ever detected.
The other hypothesis is the count : a walk with edges visits vertices, so it must repeat one, and that repeat is the cycle that can be cut out. This is why the test looks at walks of edges: with at most edges a walk can be a simple path and carry no cycle at all. The pass must be synchronous, since the proof reads as a statement about walks of at most edges. Finite weights are also assumed throughout, because the cancellation above needs sums of real numbers.
Worked passes
Worked example 4.2.6
(A negative edge without a negative cycle)
Take vertices and edges of weight , of weight , of weight , of weight , and of weight . In order the rows are
The extra row is unchanged. The best walk to is , of weight . The negative edge is allowed; a negative edge alone is not a negative cycle.
Worked example 4.2.7
(A negative cycle revealed only by the extra pass)
Take vertices and edges of weight , of weight , of weight and of weight . The cycle has weight . In order the synchronous rows are
With the extra row is , and , so . Vertices and do not improve in this pass, yet both are reachable from , so the traversal marks as having distance . The source stays at because no edge returns to it.
Worked example 4.2.8
(One vertex and a self-loop)
Take with only the source . Then and the extra pass is . If has a self-loop of weight , then , so the loop is detected and has distance . If the loop has weight or any positive weight, and no negative cycle is reported; the distance is . A zero-weight cycle is not negative and never affects finiteness.
Counterexample mode
A reachable cycle affects only its descendants
Let have weight , weight , weight , and weight . The cycle has weight , so have distance . If no edge leads back to , its distance remains . An isolated vertex is unreachable and has distance ; an unreachable negative cycle cannot affect a source distance either.
Common mistake
(Reporting the last row without the extra pass)
After passes every table entry looks like a finite answer, but a negative cycle can still be hiding. In the negative-cycle example above, looks like a valid shortest-distance table, yet the true distances to are all . Only the comparison of with shows it.
Common mistake
(Reading an in-place array as an edge-count row)
If the edges of the first worked graph are scanned in the order , , and updates are written into the same array, then after one pass the entry for is already although : the update traveled along three edges in one pass. In-place scans still converge, but their values cannot be read as at-most--edge distances, so the extra-pass test must compare genuine synchronous rows.
Cost and scope
Proposition 4.2.9
(Operation count of the edge-count algorithm)
Computing and marking the affected vertices takes arithmetic and comparison operations and working space in addition to the input graph.
Proof
(Count passes, then add one traversal)
A synchronous pass copies values and scans edges, so costs . There are passes through , for in total. Two distance arrays use extra space. The forward traversal from costs with adjacency lists, which does not change the bound. Saving every row to reconstruct bounded-edge walks would use more space. This is an operation count with constant-cost real arithmetic, not a bit-complexity guarantee for arbitrary encodings.
Exercises
Quick check
(In the first worked graph, explain why but .)
Count the edges of each route to .
Solution · Answer
With at most two edges the route costs ; the cheaper costs but uses three edges.
Quick check
(If has weight and has a self-loop of weight , what is the distance to ? Why?)
A self-loop is a cycle.
Solution · Answer
It is : after reaching , repeat the loop any number of times, lowering the walk weight without bound.
Quick check
(A negative cycle is unreachable from . Does it by itself make the source distances ?)
Ask whether a source walk can ever enter the cycle.
Solution · Answer
No. No source walk can enter that cycle, so it cannot be repeated on a source-to-vertex walk.
Quick check
(Why should the extra pass use a new array when interpreting its values as ?)
Think about what an in-place write can feed into later edges of the same pass.
Solution · Answer
In-place updates can propagate through several edges during one pass, depending on their scan order. Separate arrays enforce the at-most--edge recurrence used by the proof.