Motivation
Breadth-first search minimizes the number of edges used. When edges have different costs, that objective can disagree with minimum total cost: one expensive direct edge may lose to two inexpensive edges. We need an algorithm that compares accumulated weights rather than queue levels.
Dijkstra's rule repeatedly settles the smallest tentative distance. Why is that value safe before all routes have been examined? The answer uses nonnegative weights at an exact point in a cut argument. Merely calling the procedure greedy does not prove that its decisions are correct.
We will also separate finding an answer from checking it. A proposed list of distances, together with predecessor edges and ranks, can certify optimality using one scan of the graph. This certificate catches a failure caused by negative edges and explains why tight predecessor edges must actually lead back to the source.
Definitions
Definition 5.5.1
(Weighted walks, distances and tentative labels)
Let be a finite directed multigraph with and . Parallel arcs and loops are allowed; each arc has its own identity and finite real weight . Fix a source . A walk may repeat vertices, while a path has no repeated vertex. Its length is the sum of its arc weights. The empty walk at has length zero.
Write for the infimum of lengths of walks from to , and set it to if there is no such walk. The algorithmic results assume for every arc. The certificate theorem below explicitly allows arbitrary finite real weights.
A tentative label is either a finite candidate walk length or infinity. Settled vertices have been selected for their final labels. A relaxation of an arc from to an unsettled replaces by only when that candidate is strictly smaller, and stores that actual arc as the predecessor of . Never add a weight to an infinite label.
All mathematical comparisons are exact. We first count additions, comparisons and indexed operations; finite-bit integer costs are stated separately. This elementary version uses an array scan rather than assuming a priority-queue implementation. The unit on trees and breadth-first search supplies the unweighted reachability and BFS background.
Theorem/proposition
Theorem 5.5.2
(Nonnegative shortest walks can be chosen simple)
If all arc weights are nonnegative, every reachable vertex has a shortest path from with at most arcs. In particular its distance is finite and attained, and . Unreachable vertices have distance infinity.
Theorem 5.5.3
(The smallest tentative label is safe to settle)
Initialize , all other labels to infinity, and no vertices settled. Repeatedly select an unsettled vertex with the smallest label. Stop if that label is infinite; otherwise settle it and relax its outgoing arcs to unsettled endpoints. Ties may be broken arbitrarily.
Each settled label equals the true distance. At termination precisely the reachable vertices are settled, and their predecessor edges recover shortest paths. An array implementation uses exact operations and words including the graph.
Theorem 5.5.4
(A separately checkable shortest-distance certificate)
This assertion permits arbitrary finite real arc weights. Supply a set containing , finite labels on with , and ranks in with source rank zero. Require:
- No arc leaves for a vertex outside .
- Every arc within satisfies .
- Every other than has a predecessor arc from a vertex in , with a strictly smaller rank and equality .
Then is exactly the source-reachable set and its labels are the true distances. All other vertices are unreachable. The local conditions are checked in exact operations, without rerunning the shortest-path algorithm.
Proof sketch or proof idea
Remove cycles before claiming a minimum exists
Proof
(Delete closed subwalks, then minimize over paths)
Take any walk to a reachable vertex. If a vertex repeats, the portion between two consecutive visits is a closed walk of nonnegative weight. Delete it. The remaining walk has the same endpoints and no greater length. Repeated deletion ends because the number of arcs decreases, eventually producing a path.
There are only finitely many simple paths in a finite multigraph: each uses at most arcs, chosen from a finite set. Hence the nonempty finite family of their lengths has a minimum. The deletion argument makes that minimum no larger than any walk length, proving attainment of the distance. At the source the empty walk has length zero and no walk has negative length, so its distance is zero. Zero-weight cycles may be removed too; strict improvement during deletion is not required.
Locate the exact use of nonnegativity in the greedy proof
Proof
(Induction on settlement through the first unsettled path vertex)
At every stage a finite label is the length of an actual source walk. This is true initially for the empty walk; relaxation appends one actual arc to a previously witnessed walk. Thus a finite label cannot underestimate the true distance. It also cannot reach an unreachable vertex.
The source is selected first and is correct. Inductively suppose all earlier settled vertices have correct labels, and let be the next finite minimum. Choose a shortest path from to . On let be the first vertex not yet settled, with preceding vertex . Such an exists because is already settled. When was settled, the arc to was relaxed, since was not yet settled. Labels only decrease, so now
The first inequality is minimum selection. The next uses the earlier correct label at ; its true distance is no greater than the particular prefix to . The last inequality is where nonnegative weights are essential: the remaining suffix cannot reduce the path's total length. The walk-witness invariant supplies the reverse inequality, so equals the true distance.
If the procedure stops with infinite minimum while a reachable vertex remains, take any source path to one such vertex. Its first unsettled vertex follows a settled one, whose relaxation would give a finite label. This contradicts the infinite minimum. At most vertices are settled, so termination and the asserted reachable set follow.
Proof X-ray
Being greedy is a rule; the prefix inequality is its proof
Minimum selection compares the next vertex with the first unsettled vertex of a genuinely shortest path. Relaxation bounds that first unsettled label by a path prefix. Nonnegativity lets the prefix bound the full optimum. With a negative suffix, this last step can fail even if every earlier label was correct.
Recover a path without creating a zero-weight predecessor cycle
Proof
(Settlement ranks make predecessors acyclic)
Assign each vertex its settlement rank. A predecessor is set only by a settled vertex while its endpoint is still unsettled. The predecessor therefore has a strictly earlier rank when the endpoint is finally selected. Strict improvements overwrite the predecessor consistently with the improved label; an equal candidate leaves it alone.
Every finite nonsource label was first obtained by such a relaxation. Following predecessors strictly decreases rank and must eventually reach the source, the only settled vertex needing no predecessor. The labels are tight along these arcs. Summing their equalities shows that the recovered path has the final label as its length. Parallel arcs require keeping the actual chosen arc identity, not just its endpoints.
Zero-weight arcs do not harm this argument: ranks, not strict distance increases, prevent cycles. Choosing arbitrary tight arcs after computing distances would not give the same guarantee.
Prove the independent certificate in both directions
Proof
(Reachability from ranks, lower bounds from inequalities)
Consider any supplied certificate satisfying its three conditions. The predecessor ranks force every vertex of to have a source path within : a finite strictly descending rank chain cannot cycle, and only lacks a required predecessor. Conversely, no source walk can leave because no arc leaves it. Thus is precisely the reachable set.
For any source walk to , sum the edge inequalities along it. The intermediate labels cancel and , giving no greater than that walk's length. It is therefore a lower bound for every candidate, hence no greater than their infimum. Along the tight predecessor path, the equalities give a walk of length exactly . The infimum is consequently at most , proving equality and attainment.
Nonnegativity was not used in this certificate proof. A valid certificate can therefore verify a result in a graph with negative arcs, even though the greedy algorithm has no general guarantee there. A negative cycle outside the reachable set is irrelevant to this single-source certificate. Local tests check membership, rank bounds, predecessor identities, tightness and all arc inequalities in one vertex-and-arc scan.
The algorithm's output has this certificate. Its predecessors and ranks satisfy the conditions just proved. No arc can leave its settled set: that arc would have supplied another finite candidate before stopping. Finally true distances satisfy every edge inequality, by appending the edge to a shortest source path to its tail.
Concept lensAlgorithmic
A path gives an upper bound; inequalities give the matching lower bound
A displayed source path of cost proves only that the optimum is at most . Edge inequalities show that every competing walk costs at least . The predecessor path and the inequalities are complementary evidence. A tentative label alone does not certify optimality.
Count work in the representation actually used
Store outgoing adjacency lists, labels, predecessor arcs and settled flags. Scan all vertices to find each minimum; there are at most selections, giving quadratic scan work. Each settled vertex's outgoing list is scanned once, so total relaxation work is at most . Initialization and rank recording fit the bound. The graph and arrays use space linear in . To display one shortest path, follow its predecessor chain and reverse the list; the output can require vertices.
For integer weights between and , final finite distances are at most . A temporary relaxation candidate is safely bounded by . Labels, arc identities and loop indices fit
bits, with infinity kept as a separate flag. Charging additions, comparisons and index arithmetic by this bit length gives the corresponding factor times arithmetic work in an indexed-array model with primitive address access. Real arithmetic correctness does not by itself give a finite-precision implementation or an error bound. Faster priority-queue bounds require a separate data-structure analysis.
Worked examples
Worked example 5.5.5
(A route improves twice before it is settled)
Use vertices and arcs of weights , , , , , and . Vertex has no incident arcs.
After settling , the labels of and are and . Settle next: improves to and becomes . Settle : improves to and becomes . Settle : improves to . Then settle and stop before the infinite . The settlement order is , with labels .
The predecessor path to is of cost . The unused direct route through has cost eleven. The arc from to is not tight in the final labels: its candidate is while the true distance of is . Certificates require an inequality on every arc and tightness only on the chosen predecessor arcs.
Worked example 5.5.6
(Zero-weight ties still have acyclic predecessors)
Take arcs , , and of weight , and arcs and of weight . After settling , both and already have predecessor and label . If is settled next, its equal candidate for does not overwrite the predecessor of . It can assign label and predecessor . Settling leaves that equal candidate for unchanged.
The resulting predecessors lead back to despite the zero-weight cycle through and . Breaking the tie the other way gives another valid shortest-path tree. Equal optimal distances do not make predecessor ranks equal or permit a predecessor cycle.
Worked example 5.5.7
(A certificate can handle a negative arc)
Let , and . Supply , labels , , , and ranks with predecessor arcs and .
Both predecessor equalities hold. The remaining arc satisfies the inequality . The certificate therefore proves the distances, including the negative one, without relying on a nonnegative-weight algorithm theorem. This example does not imply that greedy settlement works on every negative-edge graph.
Common mistakes
Counterexample mode
A negative suffix defeats premature settlement
Take , and . The true distance of is , but the procedure settles at before selecting . Since settled vertices are not relaxed, it returns the wrong label for . Its proposed certificate fails on the inequality for the arc : is false. There is no negative cycle; the failure already occurs with one negative arc.
Common mistake
(BFS levels are not weighted distances)
Do not treat BFS's number-of-edges levels as weighted distances. In the first worked example, is two arcs from along , but that route costs , while the four-arc route costs .
Common mistake
(Tight predecessors that never reach the source)
Do not accept arbitrary tight predecessors as a source-path certificate. In the zero-weight example, the choices and are both tight, since the four arcs among have weight and all three labels are , yet following them from never returns to . The strict rank condition is what excludes this.
Common mistake
(Infinity is not a large finite cost)
Infinity records absence of a route, not a very large finite cost. If is replaced by a sentinel such as and weights are added to it, an unreachable vertex can receive the label , and a stopping test that looks for the sentinel value then treats it as reached.
The results concern one source; spanning trees minimizing total edge weight and negative-edge shortest-path algorithms are different problems.
Relaxing every arc in repeated rounds works whenever no negative cycle is reachable, at a higher cost.
A natural next question
What computes distances when some arcs are negative?
Relaxing every arc in repeated rounds works whenever no negative cycle is reachable, at a higher cost.
If no negative cycle is reachable from , deleting closed subwalks still cannot increase length, so shortest walks may be taken simple, with at most arcs. Relax every arc in each of rounds: after round each label is at most the least length of a source walk with at most arcs, and labels never underestimate. This Bellman–Ford procedure uses operations, and an improvement in an -th round reveals a reachable negative cycle. The certificate above can check its output.
Summary
Nonnegative weights allow shortest walks to become simple paths and justify settling the minimum tentative label. Strict relaxations from earlier settled vertices give ranked predecessor paths even with zero-weight cycles. Independently, tight rooted paths and edge inequalities certify exact distances, separating an algorithm's construction from a checkable optimality argument.
Exercises
Quick check
(In the first example change only the weight of the arc from to . Find the new distances to and a shortest path to .)
Solution · Answer
The distance of remains via . Vertex now has distance via , and has distance via . Vertex stays unreachable. After is settled, has label and can be settled before . Its candidate for is ; the later candidate through does not improve it. The new path's cost is .
Quick check
(Let be isolated and let two other vertices have zero-weight arcs in both directions. Assign all three labels zero, with and as each other’s predecessor. Why do edge inequalities and tightness hold, and why is this not a valid distance certificate?)
Solution · Answer
Every arc has weight zero and its endpoint labels agree, so all inequalities and chosen equalities hold. But neither nor is reachable from . Strict predecessor ranks would require the rank of to be smaller than that of and the rank of smaller than that of , which is impossible. The certificate's rank condition rejects the fake cycle and is what turns tight edges into actual source paths. Label correctness cannot be inferred from feasibility and local tightness alone.
Quick check
(When all arcs have weight one, explain why weighted distances equal BFS levels. Give a counterexample with and .)
Solution
With unit weights the length of every walk is exactly its number of arcs. Minimizing one is therefore minimizing the other, so the true weighted distances coincide with the reachability levels proved for BFS. Unreachable vertices are infinite in both conventions.
In the proposed weighted graph, BFS uses the direct arc as a one-edge route, but its cost is four. The two-edge route through costs two and is cheaper. Weighted distance minimization must compare accumulated costs, which is the distinction the greedy labels preserve.