= Solution
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 to
$$
w(P^T_{vu})=d(u)-d(v)=d(u),
$$
since $d(v)=0$ for positive weights. Thus the tree path is a shortest $vu$-path in $G$ for every $u$, and \b[$T$ is a <shortest-path tree> rooted at $v$].
\Image[/past-exam-of-the-short-options-course-of-the-university-of-oxford/2017-shortest-path-conventions.png]
{title=Negative weights obstruct a shortest-path tree; positive predecessors decrease distance}
{description=Original examples. In the left triangle, the two individually shortest root paths require all three edges. In the right graph, selected predecessors point strictly toward smaller root distances and therefore form a tree.}
Back to article page
