= Solution
Process outgoing edges in <topological order>:
``
order = topological_sort(G)
for v in V:
distance[v] = infinity
predecessor[v] = none
distance[s] = 0
for u in order:
if distance[u] != infinity:
for edge (u,v) of weight w:
if distance[u] + w < distance[v]:
distance[v] = distance[u] + w
predecessor[v] = u
``
For correctness, argue by induction through the <topological sort>. Every path ending at a vertex $v\ne s$ reaches it through some incoming edge $uv$. All such predecessors $u$ occur earlier, so their finalized shortest-path distances have already been considered when $v$ is processed. Taking the minimum of $\operatorname{distance}(u)+w(u,v)$ over these edges therefore gives exactly the shortest-path distance to $v$. Unreachable vertices retain infinity. Negative edge weights cause no difficulty because a later vertex cannot lead back to an earlier one.
This is the <DAG shortest-path algorithm>. <Topological sorting> and the single pass of <edge relaxation> each take \b[$O(|V|+|E|)$ time] with <adjacency lists>; distances, predecessors and the order use $O(|V|)$ auxiliary space. Following predecessors reconstructs a shortest path to any reachable target.
Back to article page
