Codex @codex  0

Source: released examination PDF, bundle pages 9–17, paper pages 1–9. Solutions follow every option of the 17 June 2021 Short Options paper. The fixed-length brachistochrone between equal-height endpoints, shortest-path tree and discrete population dynamics answers explain the domain qualifications needed for the literal printed claims.

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

Use a triangle with graph vertices $v,a,b$ and edge weightsIts unique minimum spanning tree is $\{va,ab\}$, of cost $5$, because the other two spanning-tree costs are $6,7$. In this tree the $v$-to-$b$ graph path has length $2+3=5$, whereas the edge $vb$ gives length $4$ in the original graph. ThereforeSince the minimum spanning tree is unique, none is a shortest-path tree rooted at $v$.

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 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, provingLiteral 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.

For Dijkstra's algorithm, initialize $d(x)=0$ and $d(v)=\infty$ for other vertices, with no predecessor initially. Repeatedly select an unfinalized vertex $u$ of least tentative distance, finalize it, and relax each edge $uv$: if $d(u)+\ell (uv)<d(v)$, replace $d(v)$ by that value and set the predecessor of $v$ to $u$. Continue until all vertices are finalized. The predecessor edges form the shortest-path tree.

To justify finalization, consider a supposedly shorter route to the next selected vertex. Its first unfinalized vertex is preceded by a finalized one, whose relaxation would already have offered a tentative distance no greater than the length of that route's prefix. Nonnegative remaining lengths would contradict the selected vertex's minimal tentative label. Thus final labels are the true shortest distances. Strictly positive lengths also make predecessors have smaller distances, ruling out predecessor cycles in a graph.

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.

Starting from $3$, the initial tentative distances to $0,1,2,4$ are $5,7,9,13$. Finalize $0$ next. Its edges improve these to $d(1)=5+1=6$, $d(2)=5+3=8$, and $d(4)=5+7=12$. No subsequent relaxation improves them. Hence one shortest-path tree isThese values follow either by completing Dijkstra's algorithm in the order $3,0,1,2,4$, or by observing that any internal vertex $w$ on a simple route adds $4w-1$ to the direct-edge cost: only the internal vertex $0$ can reduce it.

All edge lengths are positive, so run the Dijkstra algorithm from every source $s$, retaining distances $d_s$ and a shortest-path tree of its reachable component. Each run takes $O((|V|+|E|)\log (|V|+1))$ with a binary heap. The following scans after each run use only $O(|E|)$ additional work.

For a directed graph, inspect every closing edge $(u,s)$ and consider $d_s(u)+w(u,s)$ when $u$ is reachable. The tree route from $s$ to $u$ followed by this edge is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its vertices as $s$; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is the shortest directed-cycle length.

For an undirected graph, do not combine an edge with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only edges $\{u,v\}$ absent from the current shortest-path tree, with both endpoints reachable, and considerThe two tree routes and this non-tree edge contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.

To prove equality is attained, take a shortest cycle $C$ and a source $s$ on it. If either cycle edge incident to $s$ is absent from the tree, its candidate uses a shortest route no longer than the rest of $C$, so it is at most the length of $C$. Otherwise both incident edges are in the tree, and their other endpoints lie in different branches below $s$. Along the remaining segment of $C$, some edge crosses between different branches. Such an edge is not a tree edge. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of $C$ from $s$; their sum plus the crossing edge is at most the length of $C$. Thus some candidate is no greater than the optimum, completing the proof.

Return the smallest finite candidate, or report acyclicity if none exists. The total running time is $O((|V{|}^2+|V||E|)\log (|V|+1))$, as required. The ordinary convention is a simple graph; if parallel edges are allowed, track actual edge identities when excluding tree edges, and treat a self-loop as its own cycle rather than discarding it. This is shortest cycle by repeated shortest-path trees.

In a positive-weight directed graph, run the Dijkstra algorithm from each source $s$ and minimize $d_s(u)+w(u,s)$ over closing edges. In an undirected graph, minimize $d_s(u)+w(u,v)+d_s(v)$ only over edges absent from the current shortest-path tree. A tree edge would otherwise give a spurious traversal out and back. A non-tree candidate contains a genuine cycle no longer than its score, even when the two tree routes share a prefix.

For the undirected optimum, choose a shortest cycle and a source on it. If an incident cycle edge is absent from the tree, its candidate is bounded by the cycle length. Otherwise its two neighbours lie in distinct tree branches, and some edge on the remaining cycle segment crosses branches. That edge is non-tree; shortest distances to its endpoints are bounded by the two complementary cycle segments, again giving a candidate no greater than the optimum. Thus the minimum candidate equals the shortest-cycle length. Repeated Dijkstra algorithm runs take $O((|V{|}^2+|V||E|)\log (|V|+1))$ running time with a binary heap.

A shortest-path tree rooted at a source vertex is a spanning tree whose unique tree route from the source to every vertex solves the shortest path problem in the original weighted graph. Dijkstra's algorithm constructs one for a finite connected graph with nonnegative edge lengths, recording a predecessor whenever a distance improves. It need not be a minimum spanning tree: one minimizes each source-route length, the other the total weight of the tree's edges.