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 / ii / Solution

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.