From Distance Labels to a Route
Dijkstra’s algorithm computes shortest-distance labels from a source, but a distance alone does not say which edges form a route that attains it. Predecessor pointers retain that information compactly: each reachable vertex other than the source points to the vertex immediately before it on one chosen shortest path. Recovering a route is then a matter of following pointers backward and reversing the resulting sequence.
Throughout, \(G=(V,E)\) is a finite directed graph with a nonnegative weight \(w(u,v)\) on each directed edge \((u,v)\). The weight of a directed path is the sum of its edge weights. Fix a source \(s\). We use Dijkstra’s algorithm with tentative labels \(d[v]\), initially \(d[s]=0\) and \(d[v]=\infty\) for \(v\ne s\), and predecessor entries \(\pi[v]\), initially NIL. When a settled vertex \(u\) is processed, an edge \((u,v)\) to an unsettled vertex gives candidate \(d[u]+w(u,v)\). If this is strictly less than \(d[v]\), set \(d[v]=d[u]+w(u,v)\) and \(\pi[v]=u\). If the candidate equals \(d[v]\), retain the existing pointer in the convention used here.
We use the standard correctness result for Dijkstra’s algorithm with nonnegative edge weights: when a vertex is settled, its label equals its true shortest-path distance from \(s\); when the algorithm finishes, every reachable vertex has its shortest distance and every unreachable vertex has label \(\infty\). The task here is to interpret the predecessor information attached to those labels.
Why Following the Pointers Works
Proof. Consider a reachable \(v\ne s\). Its label begins at \(\infty\), and a finite label can be assigned only when some settled vertex \(u\) relaxes an edge \((u,v)\). At that strict improvement, the algorithm sets \(\pi[v]=u\). If a later strict improvement changes \(d[v]\), it also changes \(\pi[v]\) to the vertex responsible for that improvement. Thus the final pointer of \(v\) was assigned while its final predecessor \(u=\pi[v]\) was being processed. The label of \(u\) was final at that time, because \(u\) was settled. Therefore the final values satisfy \(d[v]=d[u]+w(u,v)\). The pointer of \(v\) always points to a vertex settled before \(v\); this remains true for the final pointer, even if \(v\)'s pointer was updated more than once. Hence, when pointers are followed backward, settlement order strictly decreases, so no vertex can repeat. The chain must end at a vertex with no predecessor. Every reachable vertex other than \(s\) has a predecessor, while \(s\) has NIL, so the chain ends at \(s\). Reversing the chain gives a directed path from \(s\) to \(v\). Summing \(d[x]=d[\pi[x]]+w(\pi[x],x)\) along its edges makes all intermediate labels cancel, leaving path weight \(d[v]-d[s]=d[v]\). By Dijkstra’s correctness result, \(d[v]\) is the shortest-path distance. Thus the recovered path is shortest. \(\square\)
This also explains the order of operations: begin at the target and follow pointers toward the source, then reverse the recorded list. The chain is not generally stored in source-to-target order.
Reconstruction Procedure
If \(d[t]=\infty\), report that no path from \(s\) to \(t\) exists. Otherwise continue.
Start with \(t\), then repeatedly append the current vertex’s predecessor, stopping when \(s\) is reached.
Reverse the list to obtain the route from \(s\) to \(t\). Check that each consecutive pair is a directed edge and that the edge weights sum to \(d[t]\).
If \(t=s\), the route is the one-vertex path \(s\), of weight \(0\); no pointer is followed. If \(t\) is unreachable, its pointer is NIL and the backward procedure must not be used. These are different cases: NIL at the source means the path has reached its start, whereas an infinite label at another vertex means no route exists.
Worked Example: Recovering a Route with Unique Shortest Distance
Let the directed weighted graph have vertex set \(V=\{s,a,b,t\}\) and edges with weights \(w(s,a)=4\), \(w(s,b)=1\), \(w(b,a)=2\), \(w(a,t)=1\), and \(w(b,t)=5\). All weights are nonnegative. Run Dijkstra’s algorithm from \(s\), using the strict-improvement pointer rule.
Initially the labels are \(d[s]=0\), \(d[a]=d[b]=d[t]=\infty\). Settle \(s\): the candidate for \(a\) is \(0+4=4\), so \(d[a]=4,\pi[a]=s\); the candidate for \(b\) is \(0+1=1\), so \(d[b]=1,\pi[b]=s\). The next smallest unsettled label is \(b\) with label \(1\). Processing \(b\) gives candidate \(1+2=3\) for \(a\), improving \(4\), so \(d[a]=3,\pi[a]=b\); it gives candidate \(1+5=6\) for \(t\), so \(d[t]=6,\pi[t]=b\). Next settle \(a\) with label \(3\). Its edge to \(t\) gives candidate \(3+1=4\), improving \(6\), so \(d[t]=4,\pi[t]=a\). Finally settle \(t\).
| Settled vertex | Labels after processing it: \(d[a],d[b],d[t]\) | Predecessors after processing it: \(\pi[a],\pi[b],\pi[t]\) |
|---|---|---|
| Initial | \(\infty,\infty,\infty\) | NIL, NIL, NIL |
| \(s\) | \(4,1,\infty\) | \(s,s,\mathrm{NIL}\) |
| \(b\) | \(3,1,6\) | \(b,s,b\) |
| \(a\) | \(3,1,4\) | \(b,s,a\) |
| \(t\) | \(3,1,4\) | \(b,s,a\) |
To recover the route to \(t\), trace \(t\leftarrow a\leftarrow b\leftarrow s\), recording \((t,a,b,s)\). Reversing gives \(s,b,a,t\). Its weight is \(w(s,b)+w(b,a)+w(a,t)=1+2+1=4\), which equals \(d[t]=4\). This verifies both that the edges form a directed path and that its weight matches the computed distance.
Tied Routes and the Meaning of One Pointer
Two or more different paths can have the same minimum weight. A single predecessor entry can display only one chosen route. With the strict-improvement rule, a candidate equal to the current label does not replace the predecessor already stored. The selected path can therefore depend on the order in which equal-label vertices are processed. That choice does not change the shortest distance.
Worked Example: Keeping One of Several Shortest Routes
Let \(V=\{s,a,b,t\}\), with directed edges of weights \(w(s,a)=2\), \(w(s,b)=1\), \(w(b,a)=1\), \(w(a,t)=2\), and \(w(b,t)=3\). Run Dijkstra’s algorithm from \(s\), keeping the existing pointer on equal candidates.
After settling \(s\), the labels are \(d[a]=2,d[b]=1,d[t]=\infty\), with \(\pi[a]=s,\pi[b]=s\). Settle \(b\) next. The candidate for \(a\) is \(1+1=2\), equal to its existing label \(2\), so \(\pi[a]\) remains \(s\). The candidate for \(t\) is \(1+3=4\), so set \(d[t]=4,\pi[t]=b\). Settle \(a\) next. Its candidate for \(t\) is \(2+2=4\), also equal to the current label, so \(\pi[t]\) remains \(b\). Then settle \(t\).
| Settled vertex | \(d[a],d[b],d[t]\) | \(\pi[a],\pi[b],\pi[t]\) |
|---|---|---|
| Initial | \(\infty,\infty,\infty\) | NIL, NIL, NIL |
| \(s\) | \(2,1,\infty\) | \(s,s,\mathrm{NIL}\) |
| \(b\) | \(2,1,4\) | \(s,s,b\) |
| \(a\) | \(2,1,4\) | \(s,s,b\) |
| \(t\) | \(2,1,4\) | \(s,s,b\) |
The pointers return \(t\leftarrow b\leftarrow s\), hence the selected route is \(s,b,t\), of weight \(1+3=4\). There is also a distinct shortest route \(s,a,t\), of weight \(2+2=4\). The route \(s,b,a,t\) has weight \(1+1+2=4\) as well. Thus three paths attain the distance \(4\), although the final table records only one of them. Each sum has been computed from the stated edge weights.
To retain alternatives, an implementation can record all edges that achieve the same best label, rather than just one predecessor. Care is needed if zero-weight edges are present: equal-distance predecessor relations can form cycles, so recursively following all such relations need not be a finite path enumeration. A single predecessor chosen on strict improvement avoids that problem and always gives the acyclic chain proved above.
The Source and Unreachable Vertices
Worked Example: Source Queries and an Unreachable Target
Let \(V=\{s,a,b,c,d\}\), with directed edges of weights \(w(s,a)=0\), \(w(s,b)=2\), \(w(a,b)=2\), and \(w(b,c)=1\). Vertex \(d\) has no incident edges. Run Dijkstra’s algorithm from \(s\), with strict improvements only.
Initially \(d[s]=0\) and all other labels are \(\infty\). Settle \(s\): the candidate for \(a\) is \(0+0=0\), so \(d[a]=0,\pi[a]=s\); the candidate for \(b\) is \(0+2=2\), so \(d[b]=2,\pi[b]=s\). Settle \(a\) next. The candidate for \(b\) is \(0+2=2\), equal to its existing label, so keep \(\pi[b]=s\). Settle \(b\): the candidate for \(c\) is \(2+1=3\), so \(d[c]=3,\pi[c]=b\). Settle \(c\). The remaining vertex \(d\) has label \(\infty\); it is unreachable and is not assigned a predecessor.
| Settled vertex | \(d[s],d[a],d[b],d[c],d[d]\) | Predecessors \(\pi[s],\pi[a],\pi[b],\pi[c],\pi[d]\) |
|---|---|---|
| Initial | \(0,\infty,\infty,\infty,\infty\) | NIL, NIL, NIL, NIL, NIL |
| \(s\) | \(0,0,2,\infty,\infty\) | NIL, \(s,s,\mathrm{NIL},\mathrm{NIL}\) |
| \(a\) | \(0,0,2,\infty,\infty\) | NIL, \(s,s,\mathrm{NIL},\mathrm{NIL}\) |
| \(b\) | \(0,0,2,3,\infty\) | NIL, \(s,s,b,\mathrm{NIL}\) |
| \(c\) | \(0,0,2,3,\infty\) | NIL, \(s,s,b,\mathrm{NIL}\) |
For a query from \(s\) to itself, the answer is the one-vertex path \(s\), whose weight is \(0\). This agrees with \(d[s]=0\), and its NIL predecessor is the stopping marker for the source. For a query from \(s\) to \(c\), tracing \(c\leftarrow b\leftarrow s\) and reversing gives \(s,b,c\), of weight \(2+1=3=d[c]\). For \(d\), the label is \(\infty\), so the correct output is “unreachable,” not a route obtained by following its NIL pointer.
Common Mistake: Reading the Chain in the Wrong Direction
A frequent error is to start at the target, follow predecessors correctly, and then report that backward list as the route. For example, in the first worked graph the chain from \(t\) is \(t,a,b,s\). It is not a directed route from \(s\) to \(t\): its first step \(t\) to \(a\) reverses the direction of the edge \(a\) to \(t\). The correction is to reverse the recorded list, giving \(s,b,a,t\). Checking each directed edge and adding its weights gives \(1+2+1=4\), the distance label of \(t\).
Another error is to replace a predecessor whenever an equal candidate appears and then assume that the output still represents every shortest path. A single pointer can represent one route only. To show there are tied routes, compare their edge-weight sums, as in the second example; do not infer that the route in the pointer table is unique.
Check Your Understanding
For each question, distinguish the stored predecessor chain from the final source-to-target route.
- If the pointer chain from \(t\) is \(t\leftarrow c\leftarrow a\leftarrow s\), what sequence should be reported as the path from \(s\) to \(t\)?
- Why does a strict improvement, rather than an equal candidate, change the predecessor in the convention used here?
- What path should be returned for a source-to-source query, and what is its weight?
- A target has label \(\infty\) and predecessor NIL. Why is this not the same situation as the source having predecessor NIL?
- Suppose the final predecessor route has edge weights \(3,0,4\). What distance label should it have, and what calculation checks the route?