A \b[<shortest-path tree>] rooted at $v$ is a <spanning tree> $T$ of $G$ for which the unique $vu$-path in $T$ is a $w$-shortest $vu$-path in $G$ for every vertex $u$. It simultaneously realizes all distances from the root. It need not be a <minimum spanning tree>, which minimizes total tree weight instead.

Solution

Past exam of the short options course of the University of Oxford / 2017 / 7 / a / iii / Solution

 Solution (source code)