A <shortest-path tree> rooted at $x$ is a <spanning tree> $T$ such that, for every <vertex> $v$, the unique $xv$ <graph path> in $T$ has minimum total <edge> length among all $xv$ <graph paths> in $G$. The objective is the sum of the lengths along each route, not the sum of all the tree's <edge> lengths.

Solution

Past exam of the short options course of the University of Oxford / 2023 / 7 / a / ii / Solution

 Solution (source code)