= Solution
For <Dijkstra's algorithm>, initialize $d(x)=0$ and $d(v)=\infty$ for other <vertices>, with no predecessor initially. Repeatedly select an unfinalized vertex $u$ of least tentative distance, finalize it, and relax each <edge> $uv$: if $d(u)+\ell(uv)<d(v)$, replace $d(v)$ by that value and set the predecessor of $v$ to $u$. Continue until all vertices are finalized. The predecessor edges form the <shortest-path tree>.
To justify finalization, consider a supposedly shorter route to the next selected vertex. Its first unfinalized vertex is preceded by a finalized one, whose relaxation would already have offered a tentative distance no greater than the length of that route's prefix. Nonnegative remaining lengths would contradict the selected vertex's minimal tentative label. Thus final labels are the true shortest distances. Strictly positive lengths also make predecessors have smaller distances, ruling out predecessor <cycles in a graph>.
Back to article page
