= Solution
Find a <topological sorting> of the <Directed acyclic graph>. Initialize $L[s]=0$ and $L[v]=-\infty$ for $v\ne s$. Process <vertices> in that order. At a reachable <vertex> $u$, update each outgoing <edge> by $L[v]\gets\max\{L[v],L[u]+w(u,v)\}$, and retain a predecessor whenever an improvement is made.
Every path to a <vertex> ends at an earlier <vertex> in the <topological sorting>. Thus, when $v$ is processed, all possible final-edge candidates for $v$ have already been considered. <Induction> along the order proves that \b[$L[v]$ is the <longest path> length from $s$], with $-\infty$ exactly for unreachable <vertices>. Signed weights cause no problem because the <graph> has no directed cycle. The <running time> is \b[$O(|V|+|E|)$], and predecessor pointers recover a maximizing path.
Back to article page
