A tentative route to a vertex is an upper bound on its shortest-path distance, not automatically a final answer. Dijkstra's algorithm identifies when one such bound is safe to finalize: choose an unsettled vertex with the smallest current tentative distance. Nonnegative edge weights make it impossible for a later route through the unsettled region to improve that choice.
The mathematical choice and the priority-queue implementation are related but distinct. A heap may contain several records for one vertex, because an old route can be superseded by a shorter one. We will prove the greedy step first, then explain which records are current, when early stopping is valid, and how predecessor edges remain meaningful when parallel edges or zero-weight cycles are present.
Define the graph and the meaning of a tentative distance
Definition 7.2.1
(Nonnegative directed shortest paths)
Let have vertices , with , and a source . Edges have nonnegative integer weights. Parallel directed edges and self-loops are allowed, and each edge has an identifier given by its position in a fixed input edge list.
Write for the minimum weight of a source-to- path, or if no path exists. The source has distance zero, witnessed by the empty path. Since all weights are nonnegative, removing a cycle cannot increase a walk's weight, so a reachable vertex has a shortest simple path.
Initialize and all other tentative labels to . Whenever a finite-label vertex is processed, relax an outgoing edge of weight by testing whether . If so, replace with that candidate and remember the edge that achieved the improvement.
Lemma 7.2.2
(Labels are upper bounds)
At every moment of the algorithm, for every vertex .
Proof
(Every finite label has a witness walk)
Every finite label is the weight of an actual discovered source walk. This is true of the source's zero label, and a relaxation replaces by , the weight of the walk witnessing extended by one edge. A walk weighs at least , so a candidate may be too large but cannot be smaller than the true optimum. Infinite labels satisfy the inequality trivially.
Definition 7.2.3
(Settled vertex)
A vertex is settled when its label has been proved final, so that , and its outgoing edges are scanned once. Unsettled labels are still tentative, even if they have already improved several times.
Prove why the smallest current label is final
Theorem 7.2.4
(The smallest unsettled label is final)
Suppose all edge weights are nonnegative. Whenever the algorithm settles a vertex , which it chooses as an unsettled vertex with the smallest finite label, the label of equals at that moment.
Proof
(Crossing the settled boundary)
The induction base is the source: its label is zero, and no nonnegative walk can have smaller weight. Assume every previously settled vertex has its true distance. Let be an unsettled vertex with the smallest finite tentative label. It is reachable because that finite label is witnessed by a source walk.
Take a shortest path from to , and let be its first unsettled vertex. Its predecessor is settled. A prefix of a shortest path is itself shortest; otherwise replacing that prefix would yield a shorter source-to- walk. When was processed, relaxing its edge to therefore gave
Together with the upper-bound invariant, this means . The remaining path from to has nonnegative weight, so . Since has the smallest unsettled label,
All inequalities are equalities, hence . Settling preserves the induction.
Proof X-ray
Which fact closes each inequality
The chain of inequalities draws on four separate facts. Minimality of the chosen label gives , because is unsettled with a finite label. The induction hypothesis, applied to the settled predecessor , gives the exact value once the upper-bound lemma is added. Nonnegativity is used exactly once, to say that the suffix from to cannot lower the weight, . The upper-bound lemma closes the loop with .
The non-obvious move is to argue about the boundary vertex rather than about itself. The label of may have been formed through unsettled vertices, so nothing is known about it directly. The vertex is one step beyond the settled region, where the relaxation has already happened, and it sits on a shortest path to . Because the chain starts and ends at , every inequality must be an equality. If a suffix could have negative weight, the middle inequality would fail, which is exactly the situation of the counterexample below.
The proof concerns finite-label reachable vertices. If the process runs out of current heap records, no reachable vertex remains unsettled: otherwise a source path to one would cross from a settled vertex to an unsettled vertex, whose relaxation would have supplied a finite label and a pending record. Unreachable vertices are never settled and retain their infinity marker.
Counterexample mode
A negative edge breaks the nonnegative-suffix argument
Use edges of weight one, of weight four and of weight . A greedy algorithm would finalize at one before processing , but the shortest route to has weight .
There is no directed cycle at all. The failure is the negative edge: the suffix from an unsettled path vertex can lower the path weight, so the middle inequality in the greedy proof is no longer justified. The implementation below rejects every negative input edge, including edges unreachable from the chosen source. Bellman–Ford addresses a different weight regime.
Keep current labels separate from heap records
Definition 7.2.5
(Heap record, current and stale)
A heap record says that a route of length to was discovered at some earlier time. It is current if and is unsettled, and stale otherwise. A stale record need not equal the current label .
Instead of changing an existing heap entry when a route improves, a lazy implementation inserts a new record and leaves the old one to be discarded later.
When a record is removed from the heap, it may settle its vertex only if the key still equals the current tentative label and the vertex has not already been settled. All obsolete or already-settled records are skipped before scanning outgoing edges.
Theorem 7.2.6
(Lazy records preserve the greedy choice)
Whenever the loop removes a heap record that is not skipped, we have , and has the smallest finite label among the unsettled vertices.
Proof
(Every unsettled label has a live record)
Whenever a label becomes finite or improves, the pair is inserted. A record leaves the heap only by being removed, and a removed record that passes both tests settles its vertex. Hence every unsettled vertex with a finite label has its record still in the heap. The heap yields the smallest record, so a removed record that passes both tests satisfies for every such . In particular , and attains the minimum.
Worked example 7.2.7
(Old heap keys survive several better routes)
Use source 0 and vertices , with this fixed edge list:
| Edge ID | Directed edge | Weight |
|---|---|---|
The two edges from 0 to 1 are distinct records. Vertices 3 and 4 form a zero-weight cycle, and vertex 5 is unreachable. Heap ties are resolved by vertex ID.
| Settled vertex | Labels afterwards, in vertex order | Main improvements |
|---|---|---|
| Vertex 1 first gets 8, then 5 | ||
| Vertex 1 improves to 3 | ||
| Vertices 3 and 4 improve | ||
| Zero edge improves vertex 4 | ||
| No strict improvement |
After settling vertex 1, old record remains and is removed before because of the vertex-ID tie. It is stale and does not rescan vertex 1. Records , and are also eventually skipped. The table records settlements, not every heap removal.
The final predecessor edge IDs are . The route to vertex 4 uses edge IDs , namely , with weight .
Zero-weight ties do not require equal-distance rewrites
Use a strict improvement test. If another route has exactly the current length, leave the label and predecessor unchanged. This finds one shortest path; it does not enumerate every shortest path or promise a lexicographically smallest one.
Theorem 7.2.8
(Predecessor chains lead back to the source)
After the run, for every reachable vertex , following predecessor edges from visits vertices settled strictly earlier at each step and ends at , even when some weights are zero.
Proof
(Predecessors settle first)
In the implementation, only a settled vertex can supply a relaxation, and a settled target is skipped. Whenever an unsettled vertex receives a predecessor edge, its predecessor is therefore already settled. If its predecessor later changes before it is settled, the new predecessor is still a vertex settled earlier than it.
After the run, every predecessor step from a reachable non-source vertex goes to an earlier-settled vertex. Following predecessor edges cannot cycle, even when some weights are zero. Since the source is the only reachable vertex with no predecessor, the chain eventually reaches it.
Store predecessor edge IDs, rather than only predecessor vertex IDs, when parallel edges exist. Two edges with the same endpoints can have different weights, so a vertex sequence alone need not identify the actual witness selected by relaxation.
A complete lazy-heap implementation
The input is a fixed list of directed triples (from_vertex, to_vertex, weight), with integer vertex IDs and integer weights as preconditions. None represents unreachable distance, separately from a legitimate zero distance. Endpoint bounds and weight nonnegativity are checked for every edge before the search; integer types are not checked at runtime. Python integers keep the example sums exact.
from heapq import heappop, heappush
def dijkstra(n, edges, source):
if n < 1 or not 0 <= source < n:
raise ValueError("a positive vertex count and valid source are required")
edges = tuple(edges)
adjacency = [[] for _ in range(n)]
for edge_id, (u, v, weight) in enumerate(edges):
if not 0 <= u < n or not 0 <= v < n or weight < 0:
raise ValueError("edge endpoints must be valid and weights nonnegative")
adjacency[u].append((v, weight, edge_id))
distance = [None] * n
predecessor = [None] * n
settled = [False] * n
distance[source] = 0
heap = [(0, source)]
while heap:
candidate, u = heappop(heap)
if settled[u] or candidate != distance[u]:
continue
settled[u] = True
for v, weight, edge_id in adjacency[u]:
if settled[v]:
continue
proposal = candidate + weight
if distance[v] is None or proposal < distance[v]:
distance[v] = proposal
predecessor[v] = edge_id
heappush(heap, (proposal, v))
return distance, predecessor
def restore_path(edges, predecessor, source, target):
if target == source:
return []
if predecessor[target] is None:
return None
path = []
while target != source:
edge_id = predecessor[target]
path.append(edge_id)
target = edges[edge_id][0]
return path[::-1]
Call restore_path with the unchanged indexed edge list and the predecessor array from the same source run, using a valid target. It returns an empty edge list for the source and None for an unreachable target. A reachable target returns its edges in forward order, each identified unambiguously. Its cost is linear in the returned path length, at most edges.
On the worked graph, dijkstra(6, edges, 0) returns distances [0,3,2,5,5,None] and predecessors [None,3,1,5,7,None]. Reconstruction for target 4 returns [1,3,5,7]; for target 5 it returns None.
Worked example 7.2.9
(The smallest instance and a zero self-loop)
Take , source and the single edge , a self-loop of weight zero. The heap starts as . Removing the record settles vertex ; scanning the loop finds its target already settled and skips it, so nothing new is inserted. The result is distance = [0] and predecessor = [None], and restore_path returns the empty list for target . The zero distance is a real value, distinct from the unreachable marker None.
Stop at settlement, not at first discovery
Counterexample mode
The first route to the target may be much longer
Use edges of weight nine, of weight two and of weight one. Processing the source discovers target with label nine. Stopping immediately on that discovery returns the wrong answer; the route through has weight three.
If only the target distance is required, stopping when a current valid record settles the target is correct by the greedy proof. At that moment, however, other unsettled labels need not be final. An early-stopping interface must not present the whole tentative array as completed shortest-path answers. The function above deliberately runs to completion.
Worked example 7.2.10
(Stopping correctly at settlement)
On the edges of weight nine, of weight two and of weight one, the heap starts with . Settling inserts and . The record is removed next and settles ; the proposal improves and inserts . Now is the smallest record and passes both tests, so is settled with distance three and a target-only search may stop. The record is still in the heap, stale, and is never examined.
Count heap records as well as vertices
Let be the number of input edge records.
Proposition 7.2.11
(Cost of the lazy-heap implementation)
The implementation inserts at most heap records. It runs in time and uses storage, including the adjacency lists and the heap.
Proof
(Counting settlements, relaxations and records)
Initialization and validation use work. Each vertex is settled at most once, so each outgoing edge is scanned at most once. There are at most successful relaxations, and hence at most insertions including the source. Every inserted record is removed at most once, at cost each.
The lazy heap may contain records, not merely one per vertex. In a multigraph, arbitrarily many parallel edges can make large while stays small, so an bound per heap operation cannot be assumed from the vertex count alone.
For example, with two vertices, list parallel source-to-target edges in strictly decreasing weight order. Scanning the source improves the target once for each edge before any target record is removed, so all those records coexist in the heap. An indexed priority queue with a decrease-key operation has a different storage and operation analysis.
The bound counts arithmetic and comparison operations; with fixed-width integers, additions must not silently overflow. Correctness rests on nonnegative weights, selecting the current smallest label, and distinguishing tentative from settled state, whatever suitable queue is used.
Common mistakes
Common mistake
(Testing a distance for falsity)
Writing not distance[v] in place of distance[v] is None mistakes a legitimate distance for unreachable. With source and edges , , , settling vertex then overwrites the correct by , and vertex is settled at distance instead of .
Common mistake
(Accepting equal-length proposals on settled vertices)
Suppose the update test were proposal <= distance[v] and settled targets were not skipped. With zero-weight edges , and , settling rewrites the predecessor of to the edge . The chain from then alternates between and and never reaches , so path reconstruction would not terminate. The strict test together with the settled check rules this out.
Exercises and worked solutions
Quick check
(Reconstruct an exact multigraph witness)
For the worked graph, give the final distance to vertex 4 and its predecessor edge chain in forward order. Why are predecessor vertex IDs alone less informative when parallel edges exist?
Solution · Answer
The distance is five. Edge IDs give with weights . A vertex pair can have several edge records with different weights, so edge IDs identify the actual selected witness rather than only its vertex sequence.
Quick check
(Choose the correct target stopping condition)
For edges , and , what is wrong with stopping when t first receives a finite label? When may a target-only search safely stop?
Solution · Answer
The first label is nine, but the shortest route has length three through . A target-only search may stop when the target is removed as a current valid minimum and settled, after skipping stale or already-settled proposals. The remaining tentative array is not thereby certified complete.
Quick check
(Interpret an obsolete heap proposal)
The heap contains after vertex 1's label has improved to three. Should removing that record scan vertex 1's edges again? If an implementation retains a settled check, is the stale-key equality test independently necessary for correctness?
Solution · Answer
It should skip the obsolete record and avoid another scan. With strict improvements and a minimum heap, the smaller fresh record must be removed before the old one. Thus a settled check already prevents the repeated scan; the explicit equality test is a clear additional current-proposal check, not an independently necessary condition in that implementation.
Quick check
(Explain why a zero-weight cycle does not make the returned path cycle)
Vertices 3 and 4 in the example have zero-weight edges in both directions. Why can following the returned predecessor edges still not loop? What happens to equal-length proposals in the code?
Solution · Answer
Every chosen predecessor was settled before its unsettled target. A predecessor chain therefore moves strictly backwards in settlement order and cannot cycle. The code skips settled targets and accepts only strict improvement, leaving equal-length proposals and the source's empty-path root unchanged.
Quick check
(Bound the lazy heap using the right parameter)
With only two vertices and m parallel source-to-target edges listed in decreasing weight order, how many target records can coexist after processing the source? Why does the vertex count not bound this heap's storage?
Solution · Answer
All target records can coexist, because each edge improves the label and inserts a new record before the next heap removal. Lazy insertion retains superseded proposals, so storage depends on edge records. A general logarithmic heap bound uses , whereas a decrease-key implementation with one item per vertex is a different data structure.
Quick check
(Distinguish zero distance, unreachability and forbidden weights)
If has weight zero and b is unreachable, what distance markers should the function return for s, a and b? Is a negative edge in an unreachable component accepted by the stated input contract?
Solution · Answer
The values are zero, zero and None. A zero-weight route is a real finite shortest path; it is not the infinity marker. The function rejects the negative edge even if unreachable, because its contract requires every input edge to be nonnegative and validation precedes traversal.