A priority queue does not decide what its keys mean. Dijkstra's algorithm orders tentative path lengths from a source; Prim's algorithm orders edges crossing a growing tree's boundary. Both can use a min-heap, but their invariants and objectives differ. This chapter traces the data structures, including stale heap entries and parent links, on an original graph.
Representing the graph and a priority queue
An undirected weighted graph consists of vertices and weighted edges. An adjacency list stores, for each vertex, its neighbors and edge weights; each undirected edge appears in both endpoints' lists. A min-heap stores entries by a specified priority and returns a smallest entry, but its backing array is not sorted. If ties matter, include a deterministic secondary key, such as a vertex name; otherwise several correct traces may exist.
Definition 14.2.1
(Tentative distance, settling and relaxation)
For Dijkstra, dist[v] is the smallest length of any discovered source-to- path, not necessarily the true shortest distance yet. A parent pointer records one path realizing that tentative value. Initially the source has distance zero and all other distances are infinity. On extracting an unsettled vertex with smallest current tentative distance, settle it and inspect its outgoing edges. Relaxing means comparing dist[u]+w(u,v) with dist[v]; a strict improvement replaces the distance and parent. In this chapter equal alternatives leave the existing parent unchanged.
Definition 14.2.2
(Lazy heap entries and stale entries)
A heap implementation may support decrease-key, changing an existing entry. A lazy implementation instead pushes a new pair on each strict improvement and leaves the old pair in the heap. On extraction, discard an entry if the vertex is already settled or the entry no longer equals its current distance. Without that check, an obsolete entry can be mistaken for new work. Infinity is a conceptual initial label; an implementation can omit unreachable vertices from the heap until a finite candidate is discovered.
Worked problem: lazy-heap shortest paths
Worked example 14.2.3
(Lazy-heap shortest paths on five vertices)
Use vertices A,B,C,D,E and undirected edges AB:2, AC:3, BC:1, BD:3, CD:1, CE:5, DE:2. Start at A. Order heap pairs by distance, then alphabetically; update only on strict improvement. Give distances, parents and the heap after each settled vertex. The lists below are heap contents in sorted-priority order, not a claim that the backing heap array is sorted.
Start with [(0,A)]. Extract A, settle it, and relax A–B and A–C: heap [(2,B),(3,C)]; parents of B and C are A. Extract B at 2. The path through B gives C length 3, equal to its existing value, so the stated tie rule keeps parent A. B–D gives 5. Heap: [(3,C),(5,D)].
Extract C at 3. C–D gives 4, improving D from 5 and changing its parent to C; C–E gives 8. The heap now contains [(4,D),(5,D),(8,E)]. Extract D at 4 and relax D–E, improving E to 6 with parent D. Heap: [(5,D),(6,E),(8,E)]. Pop (5,D) and discard it: D is already settled and the pair is obsolete. Extract E at 6, then discard stale (8,E).
The settled distances are A:0, B:2, C:3, D:4, E:6. Parents give edges AB, AC, CD, DE. The C parent could instead be B if the algorithm replaced equal-distance parents under another consistent rule; both give length 3. The distance and the identity of the selected shortest-path tree are separate outputs. The sum of these tree-edge weights is 8, but Dijkstra minimizes each root-to-vertex distance, not this sum.
Common mistake
(Trusting a popped pair without checking it)
In the trace the pair (5,D) is popped after D was settled with distance 4. An implementation that assigns the popped key to the vertex would overwrite dist[D]=4 by 5, and one that relaxes D's edges again repeats work with a wrong label. A popped pair must be discarded unless its vertex is unsettled and its key equals the current label.
Concept lensGeometric
Distance as the arrival time of a fire
Replace each edge by a segment whose length is its weight and light the source at time . A fire spreading at unit speed reaches vertex at time , the geodesic distance, and Dijkstra settles vertices in the order of arrival: the least tentative label is the next vertex the fire reaches. In the trace the fire reaches A at , B at , C at along either AC or ABC, D at and E at . A negative weight would be a fuse burning backwards in time, so nonnegativity is not a technicality.
Why settling a vertex is safe
Theorem 14.2.4
(Settling the least tentative vertex is safe)
Assume every edge weight is nonnegative, and let every settled vertex already carry its true shortest-path distance from the source. If is an unsettled vertex with a finite tentative label that is least among the unsettled vertices, then is the true distance from the source to . Consequently Dijkstra's algorithm finalizes every reachable vertex with its true distance.
Proof
(A shorter path would expose an unsettled vertex with a smaller label)
Suppose the unsettled vertex has least tentative label, but some source-to- path is shorter. On that path take the first unsettled vertex and its settled predecessor . When was settled, the edge was relaxed. The tentative label of is at most the length of the path prefix to , provided the settled label of is already correct. Because all remaining path edges are nonnegative, that prefix is no longer than the whole alleged shorter path. Hence dist[y] would be smaller than dist[u], contradicting the choice of ; if , this immediately says dist[u] < dist[u]. Induction starts at the source. If no finite unsettled label remains, undiscovered vertices are unreachable from the source.
Proof X-ray
Three hypotheses, each used once
The hypotheses enter in a fixed order. The induction hypothesis, that settled labels are true distances, gives the length of the path prefix to ; because the edge was relaxed when settled, the length of the prefix to . Nonnegative weights are used exactly once, to pass from this prefix to the whole alleged shorter path. Finally the choice of with the least label turns into a contradiction.
Remove nonnegativity and only the middle step fails. In the example below the prefix AC costs 5, while the whole path ACB costs 1.
The nonnegative assumption is doing real work.
Counterexample mode
Negative edges break the settling rule
With directed edges of weight 2, of weight 5 and of weight −4, extracting the smallest label settles B at 2 before C at 5. Yet has length 1. There is no directed cycle at all, so the failure is not caused by a negative cycle. A relaxation after B is settled cannot repair an implementation that treats settled labels as final. Use an algorithm whose hypotheses allow negative edges when the input requires them.
Prim's frontier represents cuts, not paths
Definition 14.2.5
(Frontier and stale edges in Prim's algorithm)
Prim maintains a connected set of vertices already in the tree. Its frontier consists of edges with one endpoint in and one outside. Choose a minimum-weight crossing edge, add its outside endpoint and its edge, then update the frontier. An implementation may push edges into a heap as vertices enter ; before accepting a popped edge, discard it if both endpoints are already inside. This is a different stale-entry condition from comparing a Dijkstra distance label.
Lemma 14.2.6
(Safe-edge lemma)
Let be a connected undirected weighted graph. Let be a set of edges contained in some minimum spanning tree , and let be a cut that no edge of crosses. If is a lightest edge crossing the cut, then some minimum spanning tree contains .
Proof
(Exchanging a crossing edge)
If is already in , nothing needs replacing. Otherwise, adding creates a cycle containing another edge crossing the cut. That edge is not in , because the cut crosses no edge of . Replacing it by preserves , leaves a spanning tree and cannot increase weight. The resulting tree is also minimum.
Proof X-ray
Where the cut condition protects the exchange
Each hypothesis is used once. That supplies a minimum tree to modify. The cycle made by adding must cross the cut an even number of times, so it contains a second crossing edge ; the hypothesis that no edge of crosses the cut is what guarantees , so deleting keeps . The key move is this swap, not a rebuilt tree. Finally the lightness of gives , so the weight does not increase. If were allowed to cross the cut, could belong to and the swap would destroy it.
In Prim, every edge already selected lies inside , so the current cut respects ; the lemma maintains the invariant after each choice. Ties are allowed, and different minimum trees may result.
Counterexample mode
The cut must not cross the chosen edges
Claim: if lies in some minimum spanning tree, every lightest edge across every cut extends ; the condition that avoids the cut is unnecessary. Take edges AB:2, AC:2, BC:1, (inside the minimum tree of weight ) and the cut against . Both AB and AC are lightest crossing edges, and itself crosses the cut. Choosing gives of weight , contained in no minimum tree. For a cut that respects , such as against , the lightest crossing edge is BC, and is minimum.
Worked problem: Prim on the same graph
Worked example 14.2.7
(Prim on the same graph)
Start Prim at A and use an edge heap; discard an edge whenever both ends are already in the selected set. A's frontier is AB:2, AC:3. Select AB and add B. New frontier entries include BC:1, BD:3, so select BC and add C. From C add crossing candidates CD:1, CE:5 (AC now has both endpoints selected and is stale). Select CD and add D; D contributes DE:2. Select DE and add E. The selected edges are AB:2, BC:1, CD:1, DE:2, total weight .
This tree differs from the Dijkstra tree: it uses BC rather than AC. Its path from A to C has length 3, tied with the direct edge, and its path to E has length 6, so this example happens also to have shortest root distances. The selected Dijkstra tree weighs 8, while Prim's tree weighs 6. The objectives differ even when one particular minimum spanning tree also happens to realize shortest paths from the chosen source. A minimum spanning tree is not generally a shortest-path tree, and a shortest-path tree is not generally a minimum spanning tree.
Common mistake
(A shortest-path tree is not a minimum spanning tree)
The Dijkstra tree above has edges AB, AC, CD, DE and weight 8, while the minimum spanning tree has weight 6. Shortest distances from A and minimum total weight are different objectives, and a tree that realizes one need not realize the other.
The trace does not stop because the heap is empty; it stops after all five vertices enter the tree. On a disconnected graph, Prim from A reaches only A's connected component. A minimum spanning forest needs a separate start for each remaining component, or a different explicitly specified procedure.
Worked example 14.2.8
(Unreachable and isolated vertices)
Take vertices A, B, C, D with edges AB:4, BC:1; D has no edges. Dijkstra from A settles A:0, B:4, C:5 and never discovers D, whose label stays infinite: D is unreachable. Prim from A accepts AB and then BC, with total weight 5, and the heap empties while D is outside. Restarting at D gives a tree with no edges, so the minimum spanning forest has two trees and weight 5.
Costs and checks
With adjacency lists and a lazy heap, each successful strict relaxation pushes an entry, and each directed adjacency is scanned once when its source is settled. With ordinary binary-heap operations, a conservative bound including initialization is time and space. A decrease-key heap with an appropriate vertex-position map gives the familiar bound. These bounds count comparisons and heap operations under the stated representation; a graph held as a dense matrix has different scanning costs.
Before trusting a trace, verify that each parent edge exists, each Dijkstra label equals the parent's label plus that edge's weight at finalization, and every reported reachable path starts at the source. For Prim, check that each accepted edge crosses the current cut, has minimum weight among all edges crossing that cut (ties allowed), and introduces exactly one new vertex; a connected result with edges is a tree. Neither an operation count nor a small sample proves an unqualified average-case bound. The source's separate treatment of data-structure costs still matters: the priority queue is the mechanism, while the invariant determines what it is allowed to finalize.
Why a lazy heap still extracts the current minimum
Proposition 14.2.9
(A lazy heap extracts a current minimum)
In the lazy implementation, the first pair accepted after stale pairs are discarded is for an unsettled vertex whose finite current label is least among the unsettled vertices.
Proof
(A representation invariant for the heap)
The lazy implementation maintains a concrete representation invariant: for every unsettled vertex with finite dist[v], at least one heap pair (dist[v],v) exists. The source pair establishes it initially. A strict relaxation pushes the new pair when it changes the label, so the invariant survives an update; older pairs may remain, but a label never increases. After a pop, the pair is accepted only if its key still equals the current label and its vertex is unsettled. Any unsettled vertex with a smaller finite label would have its current pair in the heap, contradicting extraction of a larger key first. Thus after stale entries are discarded, the accepted pair is a minimum current label. The heap invariant alone guarantees a smallest stored pair; the current-pair and stale-entry rules connect that fact to the abstract Dijkstra invariant.
Proposition 14.2.10
(Cost of lazy Dijkstra)
With adjacency lists and a binary heap, the lazy implementation pushes at most pairs and takes time and space.
Proof
(Counting pushes and pops)
With adjacency lists, each settled vertex's list is scanned once. Each successful strict relaxation creates at most one new pair, so the number of pushes is at most one plus the number of scanned directed adjacency entries, at most for an undirected graph. Each pair is popped at most once. A binary heap therefore gives time including initialization and space including the adjacency lists. This is a worst-case count for the stated lazy representation, not an expected hash-table bound. For a simple graph, , so ; replacing the logarithm needs that relationship, not an unstated assumption about arbitrary parallel edges. A decrease-key heap has different stored-state and operation counts.
A forest and the role of negative weights
If Prim's edge heap empties while some vertices remain outside , no edge connects to a remaining vertex; the connected component has finished. Start again at any unvisited vertex, with an empty frontier for that component. Repeating yields one minimum spanning tree per component, including an isolated vertex as a tree with no edges. The union is a minimum spanning forest: a spanning forest cannot use an edge between different connected components, and independently replacing any component tree by a lighter one would lower the total.
Negative edge weights do not invalidate Prim's cut argument. It compares crossing edge weights and uses an exchange; neither step assumes they are nonnegative. For instance, an undirected component with two vertices joined by an edge of weight has that edge as its unique spanning tree. This is distinct from shortest paths: in an undirected graph interpreted as two directed arcs, traversing a negative edge in both directions creates a negative closed walk, so a shortest-walk problem can have no finite minimum. Do not transfer Dijkstra's nonnegative-weight condition mechanically to minimum spanning trees, or transfer the cut proof to shortest paths.
Exercises with solutions
Quick check
(Replay the lazy-heap trace with a rule that replaces the parent when an equal distance is found. Which parent changes, and what is the weight of the resulting tree?)
Look at the moment B is settled.
Solution · Answer
Only the parent of C changes. When B is settled, the path A, B, C has length 3, equal to the current label, so under the new rule the parent of C becomes B. All distances are unchanged. The tree edges are AB, BC, CD, DE, with total weight , the same tree as Prim's.
Quick check
(Run Prim on the same graph starting at C, breaking ties alphabetically by the new vertex. Which edges are accepted, in order, and what is the total weight?)
Keep track of which frontier edges become stale.
Solution · Answer
From the lightest crossing edges are CB:1 and CD:1; the tie goes to B. Then CD:1 is accepted. Next BA:2 and DE:2 tie at weight 2; BA is accepted first because A precedes E, and then DE. The accepted order is CB, CD, BA, DE with total weight . The order differs from the run starting at A, but the total weight does not depend on the start vertex.
Quick check
(In the first worked trace, how many pairs are pushed in total, and how many popped pairs are discarded as stale? Compare the number of pushes with the bound .)
List the pushes in order.
Solution · Answer
The pushes are , , , , , and , so seven in total. All seven are popped, and exactly two are discarded as stale: and . The graph has edges, so the bound is , which the count respects.