= 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 \b[$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.
Back to article page
