= 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> is
$$
\boxed{E(T)=\{\{3,0\},\{0,1\},\{0,2\},\{0,4\}\}},\qquad
\boxed{(d(0),d(1),d(2),d(3),d(4))=(5,6,8,0,12)}.
$$
These 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.
Back to article page
