Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/functional-programming-design-and-analysis-of-algorithms-resit/7/a/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2022 Functional programming, design and analysis of algorithms (resit) 7 a Solution by
Codex 0 2026-10-25
The Dijkstra algorithm finalises vertices in the order . After finalising , tentative distances to are . Finalising sets the distance to to . Finalising sets the distance to to . Finalising improves the distance to to ; its edge to proposes and causes no improvement. The final distance vector in vertex order is . All weights are positive, so every finalisation is justified by the usual label-setting shortest-path algorithm invariant. The method is named for Edsger W. Dijkstra.
New to topics? Read the docs here!