Graphs are directed and finite. Unless a question explicitly changes the assumption, weights are nonnegative. Use the strict-improvement predecessor rule from the teaching chapter.
Roadmap. Start with the source at zero, relax outgoing edges, settle the smallest current label, and reconstruct a route from predecessors. Check the sign of every weight before using the proof.
Checklist. Tentative means discovered, not final. Ignore old heap snapshots. Break equal keys alphabetically for these traces. A shortest path minimizes total weight, not edge count.
1. A cheaper route arrives later
Worked example
(Settlement order when a cheaper route arrives later)
The edges are (6), (1), (2), (5), (2), (7), (1). Give the settlement order, final distances and a shortest path to . Explain why fixing at first discovery is wrong.
Solution. After , the labels are . Settle ; it improves to and discovers . Settle ; it improves to and discovers . Settle and improve to ; then settle . Old snapshots are skipped. The settlement order is , with distances respectively. Predecessors give , cost . First discovery would freeze at 6 despite the later cost-3 route.
Worked example
(Zero-weight edges and a tie)
The edges are (0), (0), (0), (2) and (2). Give the settlement order, the distances and pred[t]. After scanning , the labels are with pred[a]=s and with pred[t]=s. Settle : it discovers with pred[b]=a, and offers , which equals the current label and is not a strict improvement, so pred[t] stays . Settle : the edge points to a settled vertex and is skipped, so the zero-weight cycle creates no predecessor loop. Settle . The order is and the distances are . The route recorded by pred[t] is shortest; ties with it.
Worked example
(A target that cannot be reached)
The edges are (4), (1) and (1); the vertices and cannot be reached from . Settle and discover with pred[a]=s. Settle : the edge points to the settled source and is skipped. The heap is now empty, so the run ends with , and . Because dist[t] is infinite, the answer is that there is no route to ; pred[t] is still none, and no predecessor chain is followed.
Common mistake
(Choosing the route with the fewest edges)
A shortest path minimizes total weight, not the number of edges. In the first example the route has two edges and costs , while the shortest path has four edges and costs . A breadth-first search would return the former.
Common mistake
(Reading a tentative label as a distance)
After scanning in the first example, the label of is 6, but its distance is 3. A tentative label is only the cost of a route already discovered, so it is an upper bound on the distance until the vertex is settled.
2. A negative edge breaks the proof
Counterexample mode
A negative edge breaks settle-on-minimum
Claim: settling the vertex with the smallest tentative label is safe for every finite weight. Consider (2), (5) and (). After scanning , the labels are and , so the rule settles first at 2. Later yields the route costing , which is the true distance because these are the only two routes to in this graph. The settled value 2 is wrong. In the proof, the prefix to costs 5, greater than the complete shortest route's cost 1; with a negative final edge, a prefix need not cost at most the whole route. The repair is the hypothesis itself: a negative edge is outside Dijkstra's stated guarantee, so the weights must be nonnegative.
3. Quick checks
Quick check
(For the edges (3), (1), (1) and (1), give the settlement order, the distance to and a shortest route.)
Solution · Answer
After , the labels are and . Settle , which improves to . Settle , which discovers . Then settle . The order is , the distance to is 3, and the route is with cost ; the route costs 4.
Quick check
(In the first example, the pair is still in the heap after is settled at distance 3. What happens when it is extracted?)
Solution · Answer
It is extracted after , because its key 6 is larger. At that moment is already settled, so the pair is skipped without scanning any edge. The same happens to the old pair .
Quick check
(In the first example, which route to has the fewest edges, and what does it cost?)
Solution · Answer
The route has two edges and costs . The shortest path costs 6 and uses four edges, so the fewest-edge route is not the cheapest one.
Source: Dijkstra's algorithm.