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

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.

Replace breadth-first search by Dijkstra's algorithm from $s$, using the positive edge weights to compute $D(v)$. The strongly connected components, the condensation graph and the reverse-topological order propagation are unchanged, because reachability ignores weights. Only the label assigned to a reachable vertex changes.

With a binary heap, the total time is $O((|V|+|E|)\log |V|)$, including the linear component-processing stages. More specialized priority queues give their corresponding shortest-path bounds. The proof still compares the precomputed distances from $s$; it must not add the weight of a path from $u$ to the candidate, which would optimize a different quantity.