Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms/5/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 5 b Solution by
Codex 0 2026-10-25
Take the directed graph with source and weighted edgesIt is a Directed acyclic graph, so has no negative-weight graph cycle. The true shortest path to is , of weight .
The standard label-setting shortest-path algorithm version of the Dijkstra algorithm extracts , then at distance , then at distance , and only then at distance . Thus it finalises instead of . Even if an implementation subsequently changes the stored label of the already settled vertex , it does not reprocess its outgoing edge to , so the error at remains. Allowing repeated reprocessing would instead be a label-correcting shortest-path algorithm, not the usual Dijkstra guarantee.
New to topics? Read the docs here!