Past exam of the short options course of the University of Oxford / 2017 / 7 / d

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. ThereforeFollowing 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.

The unique root-to-$u$ path in $T$ is the reversal of its predecessor chain. Every edge satisfies $w(e_z)=d(z)-d(p(z))$. Summing along that chain telescopes tosince $d(v)=0$ for positive weights. Thus the tree path is a shortest $vu$-path in $G$ for every $u$, and $T$ is a shortest-path tree rooted at $v$.