= Solution
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 is
$$
L[v]=\max\left(0,\ \max_{(u,v)\in E}\{L[u]+w(u,v)\}\right).
$$
The 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 \b[the longest path length in the <graph>], allowing a zero-edge path. This takes $O(|V|+|E|)$, which is \b[$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_vL[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.
Back to article page
