Shortest-path predecessor ($\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.^[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.