= Shortest-path predecessor
{title2=$\pi(v)$}
A shortest-path predecessor $\pi(v)$ records the previous <vertex> on a chosen route from source $s$ to $v$. When <edge relaxation> strictly improves $d(v)$ through $u\to v$, set $\pi(v)=u$. For a <multigraph>, store the actual <directed edge>, since two <edges> with the same endpoints can have different weights. Initialize all <vertices>, including the source, without a <shortest-path predecessor>. The authored implementation reconstructs a route by following these incoming <edges> backwards, then reversing their order.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/DijkstraSP.java[Sedgewick and Wayne, DijkstraSP.java, edgeTo and pathTo]{ref}
At the end of the <edge relaxation> trace, $\pi(t)=a$, $\pi(a)=b$, and $\pi(b)=s$. Following them gives $t,a,b,s$, so the forward <directed path> is $s\to b\to a\to t$, of cost $2-1+2=3$. This makes the distance useful: a number tells us the best cost, whereas the <shortest-path predecessors> tell us which connections to take. In the <Dijkstra algorithm>, reconstruct a destination's shortest route after its label becomes permanent. In a <label-correcting shortest-path algorithm>, wait for convergence and the appropriate negative-cost <directed cycle> check. During correction, a predecessor's label may have changed since its child's last update: immediately after $b\to a$ in the trace, the current chain to $t$ costs $3$ although $d(t)$ still records the earlier discovered route of cost $8$.
Strict improvement is a useful guard against <directed cycles> in the recorded pointers. Consider $s\to a$ and $s\to b$ of cost zero, followed by $a\to b$ and $b\to a$, also of cost zero. After the first two <edge relaxations>, both labels are zero and both <shortest-path predecessors> are $s$. If equality also allows pointer replacement, the last two operations can set $\pi(b)=a$ and $\pi(a)=b$: following pointers loops forever despite correct distance labels. Keeping the old pointer on ties prevents this example; choosing among equal-cost routes requires a separate rule that preserves a route to the source. Strict improvement alone does not protect against reachable negative-cost <directed cycles>, which can force endless decreases. Equality on recorded <edges> plus the <Bellman inequalities> certifies route costs only when the pointer chains actually terminate at the source.
For all-to-one distances to $r$, record a next <vertex> $j$ whenever relaxing $i\to j$ improves $d_i$. Follow these successors forward in the original <directed graph> to reach $r$. They are <shortest-path predecessors> when viewed in the reversed <directed graph>; keeping the direction convention explicit prevents returning a route whose arrows point the wrong way.
Back to article page
