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

A tree is a connected graph with no cycles. Equivalently, between any two of its vertices there is exactly one graph path. A single vertex with no edges is also a tree.

A shortest path from $u$ to $v$ is a graph path $P$ joining these endpoints such thatfor every other $uv$-path $P^{\prime }$ in $G$, where $w(P)$ is the sum of its edge weights. Here paths have no repeated vertices; minimizing over unrestricted walks is a different problem when negative edge weights occur.

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