Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 7 / c / i

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, usingBreak 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 $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.