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

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.

Permit every vertex to start a path: initialize $L[v]=0$ for all $v$, then perform the same maximum-relaxation pass in topological sorting order. Equivalently, the recurrence isThe zero option starts a fresh, zero-edge path; the other options extend an optimal path ending at a predecessor. The largest final entry is therefore the longest path length in the graph, allowing a zero-edge path. This takes $O(|V|+|E|)$, which is $O(|V{|}^2)$ for the ordinary simple-graph representation.

If at least one edge is required, keep the same prefix values but return ${\max }_{(u,v)\in E}(L[u]+w(u,v))$ instead of ${\max }_{v}L[v]$. That variant correctly returns a negative optimum when all nonempty paths have negative weight, and reports no nonempty path if the edge set is empty. No all-pairs repetition is needed.