Both questions use finite directed graphs and nonnegative weights. Apply the snapshot heap and strict-improvement rule in the teaching chapter.
Roadmap. Follow tentative distances and tie rules through settlement. Distinguish what is known when a target is settled from what is known after a complete run. For path reconstruction, check how equal-distance updates affect predecessors.
Checklist. Zero weights are allowed. A stale snapshot is not a new settlement. Strictly earlier settlement times orient predecessor links. Early target stopping certifies the target, not every other distance.
1. Equal labels and an early stop
Worked example
(Equal labels and an early stop)
Edges are (2), (2), (2), (2), (2), (8), (8), and (1). Vertex is isolated. Break equal heap keys alphabetically and process a vertex's edges in the displayed order. Give the settlement order, all final distances and one predecessor route to . If execution stops immediately after settling , before scanning its outgoing edges, which reachable vertex remains undiscovered?
Solution. Settle and discover . Settle before ; it discovers . Settling offers equal costs to both and strict improvement leaves their predecessors unchanged. Settle , improving to 6; settle , then discover and settle . Vertex stays at infinity. Thus the settlement order is ; distances are . One route is of cost 6. The alternative through is also shortest. If we stop immediately after settling without scanning its edge, is still undiscovered although reachable; the settled target distance 6 is nevertheless correct.
Worked example
(First discovery versus settlement of the target)
The edges are (10), (2) and (3). Scanning discovers with label 10 and pred[t]=s, and with label 2. If the search stopped at the first discovery of , it would report the route of cost 10. Instead settle : the edge offers , a strict improvement, so and pred[t]=a. Now settle and stop: the target is certified at distance 5 with route . The old pair never matters, because the pair is extracted first.
Worked example
(A different tie rule changes the route, not the distances)
Use the graph of the first example, but break equal heap keys with before . Settle : . Settle first: it discovers with pred[c]=b and with pred[t]=b. Settle : its edges offer and , both equal to the current labels, so nothing changes. Settle : improves to 6 with pred[t]=c. Settle , then . The distances are exactly as before, but the recorded route is instead of . Both cost 6; the tie rule chooses which of several shortest routes is stored.
Concept lensStructural
Shortest routes as paths of tight edges
Call an edge of weight tight when for the final distances. Every shortest route uses only tight edges, because each prefix of it is itself shortest, and every route of tight edges from to costs because the terms telescope. So the shortest simple routes to are the simple paths from to in the tight subgraph. In the first example the tight edges are , , , , and , which gives the two routes to found above; is not tight. A predecessor rule picks one tight edge into each reachable vertex, and the tie rule decides which.
Common mistake
(Treating the target's first label as final)
When first receives a finite label, that label is the cost of a discovered route, not necessarily the cheapest one. In the example with of cost 10, the first label of is 10 while its distance is 5. Stop only when the current entry of is extracted and settled.
Common mistake
(Expecting an early stop to certify the other vertices)
Stopping at the settlement of certifies and the vertices settled earlier, not every vertex. In the first example, stopping right after settling leaves undiscovered, and is never reached at all. A complete table of distances needs the full run.
2. Zero-weight ties and a predecessor cycle
Counterexample mode
Updating the predecessor on a tie can create a cycle
Claim: it is harmless to update pred[v]=u when a relaxation from a settled to an already settled merely ties the current distance. Let the edges be (1), (0), (0), (1). Settle , then with pred[a]=s. Scanning discovers with pred[b]=a. When is settled, offers the equal cost 1. The proposed variant assigns pred[a]=b, leaving pred[a]=b and pred[b]=a; following predecessors alternates forever. Yet the distance values are . Under the teaching algorithm the edge into settled is skipped, and sets pred[t]=b; the route is , cost 2.
The repair is the strict-improvement rule. That algorithm sets a predecessor only while scanning an already settled vertex into an unsettled vertex on a strict improvement. The predecessor's settlement time is therefore earlier than the child's eventual settlement time. Following predecessor links strictly decreases settlement time, so no cycle is possible. Equal-cost routes can exist, but this rule records just one.
3. Quick checks
Quick check
(For the edges (1), (1) and (2), what is pred[t] under the strict-improvement rule?)
Solution · Answer
Scanning gives the label 2 with pred[t]=s. Later the edge offers , which equals the label and is not a strict improvement, so pred[t] stays . The recorded route is ; ties with it.
Quick check
(In the first example, which vertices have certified final distances if the run stops right after settling ?)
Solution · Answer
The settled vertices have final distances . The vertex is not yet discovered, and is unreachable, so neither has a certified value from this partial run.
Quick check
(For the edges (1), (0), (0), (1), how many times is each vertex settled?)
Solution · Answer
Exactly once each. The edge points to the settled vertex and is skipped, and any stale heap pair is discarded when it is extracted, so the zero-weight cycle causes no repeated settlement.
Source: Dijkstra's algorithm.