= Solution
{c}
By (i), two simple <graph paths> with different <edge> sets have different lengths. In particular two distinct simple <graph paths> from the fixed root $v$ to the same <graph vertex> $u$ have different <edge> sets, so there is a \b[unique shortest <graph path> from $v$ to each $u$]. Positive weights ensure that a shortest walk has no repeated <graph vertex>: removing a <graph cycle> strictly reduces its length.
For each $u\ne v$, take the final <edge> of its unique shortest <graph path>. Every initial segment of a shortest <graph path> is itself shortest, since replacing it by a shorter one would shorten the whole route. Thus these <edges> agree with the <graph paths>' unique predecessors. Following a predecessor strictly decreases $d_G(v,u)$, so no predecessor <graph cycle> is possible, and all <graph vertices> eventually connect to $v$. They form a <shortest-path tree>. Every other such <tree> would have to use the same unique root-to-vertex <graph paths>, proving
$$
\boxed{\text{the shortest-path tree rooted at }v\text{ is unique}.}
$$
\b[Literal wording qualification.] “Any two paths” needs a convention. Reversing an undirected <graph path> preserves its <edge> set and length; distinct zero-edge <graph paths> at different <graph vertices> also have length zero. Thus the unrestricted statement is false if these count as different <graph paths>. The proved edge-set assertion, and in particular uniqueness for <graph paths> with the same ordered endpoints, is exactly what is needed for the deduction. Arbitrary walks are not included.
Back to article page
