Solution

ID: 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 and for . Process vertices in that order. At a reachable vertex , update each outgoing edge by , 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 is processed, all possible final-edge candidates for have already been considered. Induction along the order proves that is the longest path length from , with exactly for unreachable vertices. Signed weights cause no problem because the graph has no directed cycle. The running time is , and predecessor pointers recover a maximizing path.

New to topics? Read the docs here!