= Solution
First run <breadth-first search> from $s$ to compute each distance $D(v)$. All are finite by hypothesis. Next compute the <strongly connected components> and their <condensation graph> $H$. For every component $C$, initialize a representative $b(C)$ minimizing $D(v)$ over $v\in C$. Process components in reverse <topological order>, using
$$
b(C)=\operatorname*{arg\,min}_{x\in\{b(C)\}\cup\{b(B):C\to B\text{ in }H\}}D(x).
$$
Break equal-distance ties consistently, for example by fixed vertex index. Return $b(C)$ for every $u\in C$.
Every <vertex> of one <strongly connected component> reaches every other; every reachable different component is reached through some first outgoing <edge> of $H$. Since $H$ is a <Directed acyclic graph>, reverse <topological order> has already solved every successor. <Induction> over that order proves that the representative minimizes $D$ over all reachable <vertices>. This is <minimum reachable label propagation>.
All stages take \b[$O(|V|+|E|)$ time] and $O(|V|+|E|)$ space with explicit <adjacency lists>. Retaining parallel component edges is harmless: they can be scanned once each without sorting or deduplication. Reachability here includes the length-zero path, so $u\in P(u)$; this standard convention also makes the requested answer meaningful at a sink.
Back to article page
