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

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!