A direct road with cost 7 can be worse than two roads with costs 2 and 1. BFS counts edges, so it cannot generally choose the cheapest weighted route. Dijkstra's algorithm keeps the cost of the cheapest route discovered so far and always settles the smallest current tentative cost.
This lesson extends the existing Dijkstra lesson with a snapshot-heap implementation, a detailed trace and short worked practice.
1. The contract and an implementation
Let be a finite directed graph with source , and let all edge weights be nonnegative real numbers. Zero-weight edges are permitted. An undirected edge may be represented by two directed adjacency entries. Parallel edges are separate entries. We seek the minimum sum of weights from to each vertex; unreachable vertices have distance .
Definition
(Tentative label, relaxation and settled vertex)
A finite tentative dist[v] is the cost of a discovered walk and hence an upper bound on the true distance. A successful relaxation through an edge replaces dist[v] if dist[u] + weight(u,v) is strictly smaller. Record pred[v]=u on that strict improvement. A vertex is settled when it is extracted from the heap with a current key; its label is not changed afterwards.
The implementation below uses a min-heap of immutable (distance, vertex) snapshots. Break equal keys alphabetically only to make traces reproducible; correctness does not require that tie rule.
for v in V: dist[v] = infinity; pred[v] = none; settled[v] = false
dist[s] = 0; heap = [(0,s)]
while heap is not empty:
(k,u) = extract_min(heap)
if settled[u] or k != dist[u]: continue
settled[u] = true
for each edge (u,v,w) leaving u:
if not settled[v] and k+w < dist[v]:
dist[v] = k+w; pred[v] = u
insert(heap, (dist[v],v))
return dist, pred
A later improvement does not change an older heap snapshot. When the old pair is extracted, the stale/settled check prevents another edge scan. Equal candidate distances do not replace predecessors under this specified rule. Every finite label comes from an actual discovered walk; infinity is a mathematical sentinel, and an implementation must handle it without unsafe arithmetic.
2. Why the smallest current label is safe
Theorem
(Correctness of Dijkstra's algorithm)
Let all edge weights be nonnegative. When a vertex is settled with key , then , the true distance from to . Consequently, when the algorithm halts, dist[v] equals for every reachable vertex , and dist[v] is infinity for every unreachable one.
Proof
(Induction over the settlement order)
Assume all previously settled labels are true shortest distances. Let be the next vertex settled, with current key . Its discovered route gives . Suppose . Choose a shortest path to and let be its first unsettled vertex, with settled predecessor . Nonnegative weights ensure the path's prefix cost to is at most ; that prefix is itself shortest to . When was settled, relaxation made dist[x] at most that prefix cost, and a finite tentative label cannot be below the true shortest distance. Thus dist[x] = delta(x) <= delta(u) < k.
If , this contradicts the current-entry check k == dist[u]. Otherwise has a current heap snapshot: a current snapshot cannot have been extracted earlier without settling . Its smaller key would be extracted before , contradicting the min-heap rule. Hence . The source starts at zero, completing the induction. This proof uses nonnegative weights when comparing the prefix with the full route; the greedy argument does not extend unchanged to negative edges.
Proof X-ray
Where each hypothesis enters the settlement proof
The proof is a contradiction at the first wrong settlement, and each hypothesis is used at one identifiable step. The induction hypothesis, that every earlier settled label is exact, makes the settled predecessor of exact, so relaxing leaves dist[x] at most the prefix cost. Nonnegative weights are used in exactly one inequality, : the prefix of a shortest path to cannot cost more than the whole path. With a negative final edge this link fails, and so does the theorem. The fact that no finite label lies below a true distance upgrades dist[x] from an upper bound to the exact value . The heap order is used last: the current snapshot of has a key below , so it would be extracted before , which contradicts the choice of . The case is closed by the check k == dist[u]. The argument closes because is impossible, so every settlement is exact, and the induction ends since each vertex is settled at most once.
Proposition
(Predecessor chains)
After the algorithm halts, for every reachable vertex , the vertex pred[v] was settled before , following predecessor pointers from reaches in finitely many steps, and the reversed sequence is a shortest path from to . This holds also when zero-weight edges are present.
Proof
(Predecessors point backwards in settlement time)
A strict-improvement predecessor always points from an unsettled vertex to a vertex already settled when the pointer is set. Following final predecessor pointers moves backwards in settlement time, so it cannot cycle even with zero-weight edges. Moreover, when pred[v]=u was last set, dist[v]=dist[u]+weight(u,v) held and dist[u] was already final, so along the chain the weights telescope to dist[v], which equals by the theorem. For a reachable non-source target, follow predecessors to and reverse the sequence. If dist[target] is infinity, report no route. Keeping one predecessor gives one shortest route, not necessarily all tied routes.
3. Worked trace
Worked example
(Trace with stale snapshots)
Use edges (7), (2), (1), (6), (1), (8), (3). Alphabetical order breaks equal heap keys. The table records current finite distances after scanning each settled vertex.
| Settled | |||||
|---|---|---|---|---|---|
| 0 | 7 | 2 | |||
| 0 | 3 | 2 | 8 | ||
| 0 | 3 | 2 | 4 | 11 | |
| 0 | 3 | 2 | 4 | 7 | |
| 0 | 3 | 2 | 4 | 7 |
The old pair is removed and skipped before because is already settled; the old and are skipped later. The predecessor chain for is . Reversing it yields with cost .
Concept lensGeometric
Settled vertices form a growing ball
Imagine a fire that starts at and crosses each edge in a time equal to its weight, so that ignites at time . Keys are extracted in nondecreasing order, and for every radius the vertices settled with key at most are exactly the ball . In the trace, radius holds (with ) and radius adds . A tentative label is the predicted ignition time of a vertex just outside the ball, reached along an edge leaving it. Nonnegative weights are what make time run forward: a negative edge would let a vertex ignite before its source.
Worked example
(Zero-weight edges and a stale snapshot)
Use edges (0), (0), (5) and (0). Settle : it discovers with pred[a]=s and with pred[b]=s. Settle : the edge offers , a strict improvement, so and pred[b]=a, and the new pair is inserted. Settle : it discovers with pred[t]=b. Settle . The old pair is extracted last and skipped, because is settled. All distances are 0, and the predecessor chain is the route of cost 0.
Worked example
(An unreachable vertex and an edge into the source)
Use edges (4), (1) and (2); the vertex cannot be reached from . Settle and discover with pred[a]=s. Settle : the edge points to the settled source and is skipped, because settled vertices are never relaxed. The heap is empty, so the run ends with , and , with pred[c]=none. The edge is never scanned, because is never settled.
Common mistake
(Reading a tentative label as a distance)
After scanning in the trace, dist[a]=7, but the distance from to is 3. A tentative label is the cost of a route already found, so it is only an upper bound until the vertex is settled.
Common mistake
(Scanning the edges of a stale pair)
If the check settled[u] or k != dist[u] is omitted, the old pair would scan the edges of a second time. No label can improve through it, because its key is not smaller than the exact label, so the output is unchanged. The cost is not: a vertex may then be scanned once per snapshot, and the bound of one scan per adjacency entry, and with it the running time bound below, is lost.
4. Cost and stopping
Proposition
(Running time with a snapshot heap)
With adjacency lists, exact constant-time arithmetic and a binary min-heap, the algorithm runs in time and uses auxiliary space, excluding the storage of the graph.
Proof
(Counting scans, insertions and heap operations)
Assume adjacency lists, exact constant-time arithmetic and a binary min-heap. Initializing arrays costs . Each vertex is settled once and each outgoing adjacency entry is scanned at most once. There are at most successful relaxations and hence at most inserted snapshots. Heap work is . Total time is , including disconnected and empty-edge cases. The arrays and heap use auxiliary space, excluding graph storage.
An indexed heap with decrease-key has a different space and operation count; do not silently transfer one implementation's bound to another.
If only one target distance is needed, stopping when its current entry is extracted and settled is correct. Stopping at first discovery is not: a cheaper route can arrive later. Early stopping does not compute all other distances, and stopping before scanning the target's outgoing edges can leave reachable vertices undiscovered.
Counterexample mode
The first finite label of the target is not its distance
Claim: the search may stop as soon as the target receives a finite label. In the trace above, first receives a label when is settled: the edge gives with pred[t]=a. Stopping there would report the route of cost . But settling later improves to , and the true distance is 7, by the route . The repair is to stop only when the current pair of is extracted and settled; in the trace, that is the pair .
5. Quick checks
Quick check
(Run the algorithm on the edges (4), (1), (2) and (1). Give the distance to and its predecessor chain.)
Solution · Answer
After , the labels are and . Settle , which improves to 3. Settle , which discovers . Then settle . The distance to is 4, the chain is , and the route costs .
Quick check
(In the worked trace, how many snapshots are inserted in total, and how many of them are stale when extracted?)
Solution · Answer
The source pair is inserted first, and every one of the 7 edges produces a successful relaxation, so snapshots are inserted. Five of them settle . The other three, , and , are stale and are skipped.
Quick check
(In the worked trace, how many times is pred[a] assigned, and why does it not change again?)
Solution · Answer
Twice: pred[a]=s when is scanned (label 7), and pred[a]=b when is scanned (label 3, a strict improvement). After is settled, no relaxation targets it, so its predecessor is final.