= Solution
Let $d(u)$ be the weight of a shortest $vu$-path, and let $p(u)$ be the predecessor of $u$ on the chosen $P_u$. Its prefix to $p(u)$ must also be shortest: a cheaper prefix followed by the final edge would give a cheaper walk to $u$, and <cycle erasure in minimum-weight walks> would produce a cheaper path because every edge weight is positive. Therefore
$$
d(u)=d(p(u))+w(e_u)>d(p(u)).
$$
Following predecessor arrows strictly decreases $d$, so cannot revisit a vertex. Since each nonroot vertex has a predecessor, finiteness forces every predecessor chain to end at $v$. Thus $T$ is connected.
The edges $e_u$ are distinct: if two vertices selected the same undirected edge, each would be the other's predecessor, contradicting strict decrease. Hence $T$ has exactly $|V(G)|-1$ edges. A finite connected graph with this edge count is a tree. This proves that <positive-weight shortest-path predecessors form a tree>, without requiring the initially chosen paths to be mutually consistent.
Back to article page
