Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8 / c / i / 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]\leftarrow \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 $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 $O(|V|+|E|)$, and predecessor pointers recover a maximizing path.