= Positive-weight shortest-path predecessors form a tree
{title2=$d(u)=d(p(u))+w(p(u)u)>d(p(u))$}
In a finite connected graph with strictly positive edge weights, choose any <shortest path> from a root $v$ to every other vertex $u$, and let $p(u)$ be its penultimate vertex. Every prefix is shortest: a better prefix followed by the final edge would give a cheaper walk, whose positive-weight cycles can be erased to give a cheaper path. Thus the displayed distance identity holds.
Following predecessors strictly decreases the shortest-path distance, so no predecessor cycle is possible. Since every nonroot vertex has a predecessor, every chain reaches the root. Opposite predecessor choices cannot select the same undirected edge, again by strict distance decrease. The selected graph is connected and has exactly one edge per nonroot vertex, so is a <spanning tree>. Along its root paths the distance differences telescope, proving that it is a <shortest-path tree> even if the original shortest paths were chosen independently.
Back to article page
