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

The Dijkstra algorithm finalises vertices in the order $1,3,2,5,4$. After finalising $1$, tentative distances to $2,3$ are $3,2$. Finalising $3$ sets the distance to $5$ to $4$. Finalising $2$ sets the distance to $4$ to $6$. Finalising $5$ improves the distance to $4$ to $5$; its edge to $2$ proposes $5$ and causes no improvement. The final distance vector in vertex order is $(0,3,2,5,4)$. 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.