= Solution
The <Dijkstra algorithm> finalises <vertices> in the order \b[$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 \b[$(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>.
Back to article page
