Why a Settled Distance Is Final
Dijkstra’s algorithm repeatedly chooses an unsettled vertex with the smallest finite distance label and declares that label final. The important question is why no route through vertices that have not yet been selected can later improve it. The answer is the settled-set invariant: labels for unsettled vertices record the best routes whose internal vertices are already settled. Nonnegative edge weights then ensure that a route which leaves the settled set cannot return with a smaller total cost.
Throughout, let \(G=(V,E)\) be a finite directed graph with no loops or multiple edges, and let each edge \(e\) have a weight \(w(e)\ge 0\). Fix a source \(s\). A walk is a sequence of vertices joined by directed edges in the indicated direction; its length is the sum of the weights of those edges. A path is a walk with no repeated vertices. The distance \(D(s,v)\) is the minimum length of an \(s\)-\(v\) path, or \(\infty\) if no such path exists. Because weights are nonnegative, removing a repeated-vertex segment from a walk never increases its length. Thus, whenever \(v\) is reachable, a shortest path exists among the finitely many paths with no repeated vertices.
Any finite label produced by this procedure is the length of an actual route from \(s\): initially this holds for the source, and each relaxation extends a route by one edge. In particular, for every reachable vertex with finite label, \(D(s,v)\le d[v]\). A label is therefore an upper bound on the true distance, not automatically the true distance. Proving that selected labels are exact is the central task.
The Settled-Set Invariant
An internal vertex of a walk is any vertex other than its two endpoints. The second part says precisely which routes a tentative label has already considered: they may pass through settled vertices, but not through an unsettled internal vertex. At initialization \(S=\varnothing\). The only such walks to a vertex other than \(s\) are direct edges from \(s\), and the zero-length walk gives the label of \(s\), so the invariant holds.
Proof. We prove the assertion about each selected vertex and the invariant together, one iteration at a time. If \(u=s\) is selected first, then \(d[s]=0=D(s,s)\), since all edge weights are nonnegative and the zero-length walk has length \(0\). Now consider any later selected vertex \(u\), and let \(S\) be the settled set just before \(u\) is selected. Take a shortest \(s\)-\(u\) path \(P\). Since \(s\in S\) and \(u\notin S\), let \(y\) be the first vertex of \(P\) outside \(S\), and let \(x\) be its predecessor on \(P\). Then \(x\in S\), and the edge \(xy\) was relaxed when \(x\) was settled. The part of \(P\) from \(s\) to \(y\) has internal vertices in \(S\). By the invariant, \(d[y]\) is no greater than the length of that part. Since the remaining edges of \(P\) have nonnegative weights, that prefix length is no greater than \(D(s,u)\). The selection rule gives \(d[u]\le d[y]\), so \(d[u]\le D(s,u)\). On the other hand, a finite label is the length of an actual route, and therefore \(D(s,u)\le d[u]\). Hence \(d[u]=D(s,u)\).
It remains to check that the invariant’s second part is maintained after settling \(u\) and relaxing its outgoing edges. Fix a vertex \(v\) still unsettled. Before \(u\) was added, the old label \(d[v]\) was the minimum length of a walk whose internal vertices lie in \(S\). The new walks allowed by the enlarged set \(S\cup\{u\}\) either avoid \(u\) as an internal vertex, or use \(u\). A walk avoiding \(u\) was already allowed. If a simple allowed path uses \(u\) and goes directly from \(u\) to its endpoint \(v\), its prefix ending at \(u\) has internal vertices in \(S\), so its length is at least \(d[u]\); relaxation of \(uv\) considers a route of length \(d[u]+w(uv)\), no greater than that path’s length.
There is one other case: after visiting \(u\), the path may next visit a vertex \(x\in S\), and only later reach \(v\). It need not use an edge \(uv\). The old label \(d[v]\) is already no greater than this path’s length. Indeed, \(d[x]=D(s,x)\), so \(d[x]\) is no greater than the path’s prefix length from \(s\) to \(x\). Take a route realizing \(d[x]\), then append the path’s suffix from \(x\) to \(v\). The resulting walk has all internal vertices in \(S\), so the old invariant implies that \(d[v]\) is no greater than its length, which in turn is no greater than the original path’s length. Thus every newly allowed path is accounted for by the old label or by a relaxation from \(u\). Conversely, every finite candidate label is realized by an allowed walk. Taking the minimum of the old label and the relaxation candidates gives exactly the minimum length among walks whose internal vertices lie in \(S\cup\{u\}\). The invariant is preserved.
Finally, if the algorithm stops with some reachable vertex \(v\) unsettled, take a path from \(s\) to \(v\) and its first vertex \(y\) outside \(S\). Its predecessor \(x\) lies in \(S\). When \(x\) was settled, relaxing \(xy\) gave \(y\) a finite label, and that label remains finite thereafter. This contradicts the stopping rule that no unsettled vertex has a finite label. Thus every reachable vertex is settled, and every unsettled vertex is unreachable. \(\square\)
Tracing the Invariant
Worked Example: A Sequence of Strict Improvements
Consider the directed weighted graph with \(V=\{s,a,b,c,d\}\) and edges \(s\to a\) of weight \(4\), \(s\to b\) of weight \(1\), \(b\to a\) of weight \(2\), \(a\to c\) of weight \(1\), \(b\to c\) of weight \(5\), \(c\to d\) of weight \(3\), \(a\to d\) of weight \(7\), and \(b\to d\) of weight \(10\). The table gives labels after relaxing the selected vertex; \(\infty\) means no finite label yet.
| Selected vertex | Settled set after selection | \(d[a]\) | \(d[b]\) | \(d[c]\) | \(d[d]\) |
|---|---|---|---|---|---|
| Initial labels | \(\varnothing\) | 4 | 1 | \(\infty\) | \(\infty\) |
| \(s\) (label 0) | \(\{s\}\) | 4 | 1 | \(\infty\) | \(\infty\) |
| \(b\) (label 1) | \(\{s,b\}\) | 3 | 1 | 6 | 11 |
| \(a\) (label 3) | \(\{s,b,a\}\) | 3 | 1 | 4 | 10 |
| \(c\) (label 4) | \(\{s,b,a,c\}\) | 3 | 1 | 4 | 7 |
| \(d\) (label 7) | \(\{s,b,a,c,d\}\) | 3 | 1 | 4 | 7 |
Initially, \(d[a]=4\) and \(d[b]=1\), from the two edges out of \(s\). The minimum is \(b\), so relax its outgoing edges: \(d[a]=\min(4,1+2)=3\), \(d[c]=\min(\infty,1+5)=6\), and \(d[d]=\min(\infty,1+10)=11\). Next \(a\) is selected with label \(3\). Its relaxations give \(d[c]=\min(6,3+1)=4\) and \(d[d]=\min(11,3+7)=10\). Selecting \(c\) with label \(4\) gives \(d[d]=\min(10,4+3)=7\). Vertex \(d\) is then selected.
Check: The selected distances are realized by \(s\), \(s\to b\) of length \(1\), \(s\to b\to a\) of length \(1+2=3\), \(s\to b\to a\to c\) of length \(1+2+1=4\), and \(s\to b\to a\to c\to d\) of length \(1+2+1+3=7\). The incoming-edge candidates independently confirm the minima: for \(a\), \(\min(4,1+2)=3\); for \(c\), \(\min(3+1,1+5)=4\); and for \(d\), \(\min(3+7,1+10,4+3)=7\).
Worked Example: Zero-Weight Edges and a Tie
Let \(V=\{s,a,b,c\}\), with directed edges \(s\to a\) of weight \(0\), \(s\to b\) of weight \(0\), \(a\to b\) of weight \(0\), \(b\to a\) of weight \(0\), \(a\to c\) of weight \(2\), and \(b\to c\) of weight \(2\). A tie between \(a\) and \(b\) can be settled in either order; choose \(a\) first.
After settling \(s\), the labels are \(d[a]=0\), \(d[b]=0\), \(d[c]=\infty\). Select \(a\), one of the two minimum-label vertices. Relaxing \(a\to b\) leaves \(d[b]=\min(0,0+0)=0\), and relaxing \(a\to c\) gives \(d[c]=\min(\infty,0+2)=2\). Now select \(b\) with label \(0\). Its edge to \(a\) does not change the settled label of \(a\), and its edge to \(c\) gives \(d[c]=\min(2,0+2)=2\). Finally select \(c\) with label \(2\).
Check: The routes \(s\to a\) and \(s\to b\) both have length \(0\). Routes to \(c\) through either \(a\) or \(b\) have length \(0+2=2\). The zero-weight edges therefore create a tie and allow a zero-cost cycle, but they do not invalidate the proof: nonnegative weights, including zero, are all that is required.
Worked Example: An Unreachable Vertex in a Directed Graph
Let \(V=\{s,p,q,r,z\}\), with edges \(s\to p\) of weight \(2\), \(p\to q\) of weight \(2\), \(q\to p\) of weight \(0\), \(s\to r\) of weight \(7\), and \(z\to s\) of weight \(1\). The direction of the last edge matters: it leads from \(z\) to \(s\), not from \(s\) to \(z\).
After settling \(s\), the labels are \(d[p]=2\), \(d[r]=7\), \(d[q]=\infty\), and \(d[z]=\infty\). Settle \(p\) with label \(2\); relaxing \(p\to q\) gives \(d[q]=2+2=4\). Settle \(q\) with label \(4\); the candidate for \(p\) is \(4+0=4\), which does not improve its settled label \(2\). Settle \(r\) with label \(7\). No unsettled vertex has a finite label, so the algorithm stops with \(z\) unsettled.
Check: The paths \(s\to p\) and \(s\to p\to q\) have lengths \(2\) and \(2+2=4\), respectively, and the direct path \(s\to r\) has length \(7\). There is no directed path from \(s\) to \(z\); the edge \(z\to s\) cannot be traversed in reverse. The stopping conclusion therefore agrees with the graph’s directions.
A Common Proof Pitfall
When proving that labels remain correct after settling \(u\), it is not enough to say that every newly allowed path through \(u\) ends with an edge \(uv\). A path may leave \(u\), visit a vertex that was already settled, and only then reach \(v\). Such a path is not captured by relaxing \(uv\).
For a concrete case, take \(V=\{s,x,u,v\}\) and edges \(s\to x\) of weight \(0\), \(s\to u\) of weight \(1\), \(u\to x\) of weight \(0\), and \(x\to v\) of weight \(0\). After settling \(s\), the labels are \(d[x]=0\), \(d[u]=1\), and \(d[v]=\infty\). Settle \(x\) next; relaxing \(x\to v\) gives \(d[v]=0+0=0\). Then \(u\) is selected. The route \(s\to u\to x\to v\) has length \(1+0+0=1\), but there is no edge \(u\to v\), so a proposed relaxation candidate \(d[u]+w(uv)\) is not even defined. The correction is to use the old label: \(d[v]=0\le 1\), because the route through the already settled vertex \(x\) has already been considered. This is exactly why the invariant-preservation proof must include paths that return from \(u\) to the settled set.
The settled-vertex invariant matters because it supplies the missing justification behind Dijkstra’s selection rule: the smallest tentative label is not merely the best route found so far, but the true shortest-path distance. The argument depends on nonnegative weights when it compares a shortest path’s prefix with its total length. It also handles ties and unreachable vertices without requiring every vertex to be reachable from the source.
Check Your Understanding
Use the invariant and the selection proof to answer these questions.
- In the invariant, what restriction is placed on the internal vertices of a walk used to define an unsettled vertex’s label?
- Why does a finite tentative label imply \(D(s,v)\le d[v]\)?
- In the proof for a path that visits \(u\) and then a previously settled vertex \(x\), why can the old label \(d[v]\) already account for that path?
- Which step of the selected-vertex proof uses the assumption that edge weights are nonnegative?
- Suppose the algorithm stops with an unsettled vertex \(v\) that is claimed to be reachable. Explain how the first unsettled vertex on a path to \(v\) contradicts the stopping rule.