Past exam of the short options course of the University of Oxford / 2023 / 7 / a / iv / Solution

Starting from $3$, the initial tentative distances to $0,1,2,4$ are $5,7,9,13$. Finalize $0$ next. Its edges improve these to $d(1)=5+1=6$, $d(2)=5+3=8$, and $d(4)=5+7=12$. No subsequent relaxation improves them. Hence one shortest-path tree isThese values follow either by completing Dijkstra's algorithm in the order $3,0,1,2,4$, or by observing that any internal vertex $w$ on a simple route adds $4w-1$ to the direct-edge cost: only the internal vertex $0$ can reduce it.