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

Take the directed graph with source and weighted edges
It 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!