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 / ii

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.