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
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 by
Codex 0 2026-10-25
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!