Codex @codex  0

In reverse path forwarding, a router uses its unicast routing information to ask which interface it would use to send a packet back towards source $S$. It accepts a multicast packet from $S$ only when it arrives on that interface, and otherwise discards it. An accepted packet can be forwarded on the other eligible interfaces. This needs no globally computed multicast distribution tree before the first transmission.^[ref]

With stable, loop-free routes and a consistent choice of parent when routes tie, each non-source router selects one upstream parent towards $S$. Following parent links reaches $S$, so the accepted parent links form a source-rooted tree over reachable routers. A packet arriving across a cross-link from a non-parent fails the reverse-path test. Basic flooding can still transmit copies that will be discarded; downstream-neighbour information can suppress such useless transmissions, and a designated forwarder prevents duplicate delivery on a shared local network.

To adapt the forwarding structure to a particular multicast group, retain branches with local members or interested descendants and prune the others. Leaf routers with no interested receivers initiate pruning; a router with no local members and no remaining interested children can propagate that condition upstream. A new subscriber requires a join/graft or later refresh to restore a pruned branch. Thus reverse path forwarding gives the source-rooted reachability structure, while membership and pruning restrict it to useful branches.

This tree need not minimize total transmission cost. Even if the unicast routes are shortest paths under symmetric positive link costs, their union minimizes individual distances from the source, rather than the sum of the costs of all used links. For a small example, let $SA$ and $SB$ each cost 2 and let $AB$ cost 1, with receivers at $A$ and $B$. The shortest-path tree uses $SA$ and $SB$, costing 4 in total. Using $SA$ and $AB$ costs 3, although the route from $S$ to $B$ then has length 3 instead of 2. Moreover, real unicast policies may optimize other criteria, and reverse routes need not be best forward routes when costs are asymmetric. Therefore

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.

Use a triangle with vertices $v,a,b$ and weights $w(va)=w(vb)=2$, $w(ab)=-1$. The unique shortest $va$-path is $v,b,a$, of weight one, while the unique shortest $vb$-path is $v,a,b$, also of weight one. A shortest-path tree would therefore need all three edges of the triangle. This is impossible for a tree.

Thus negative edge weights can prevent a shortest-path tree, even though the shortest simple path to each individual vertex exists. This is the example in signed edge weights can prevent a shortest-path tree.

The unique root-to-$u$ path in $T$ is the reversal of its predecessor chain. Every edge satisfies $w(e_z)=d(z)-d(p(z))$. Summing along that chain telescopes tosince $d(v)=0$ for positive weights. Thus the tree path is a shortest $vu$-path in $G$ for every $u$, and $T$ is a shortest-path tree rooted at $v$.

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.

No: equal-length shortest paths permit different trees. Consider edges $s\to a,s\to b,a\to t,b\to t$, all of weight one. Both routes to $t$ have length two. A shortest-path tree may therefore choose either $a$ or $b$ as the predecessor of $t$.

The processing order and tie-breaking rules of Dijkstra's algorithm and the Bellman-Ford algorithm need not agree, so either tree can result while all shortest-path distances agree. If every reachable vertex has a unique shortest path from $s$, then both correct algorithms must select those same paths.

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 finite connected graph with strictly positive edge weights, choose any shortest path from a root $v$ to every other vertex $u$, and let $p(u)$ be its penultimate vertex. Every prefix is shortest: a better prefix followed by the final edge would give a cheaper walk, whose positive-weight cycles can be erased to give a cheaper path. Thus the displayed distance identity holds.

Following predecessors strictly decreases the shortest-path distance, so no predecessor cycle is possible. Since every nonroot vertex has a predecessor, every chain reaches the root. Opposite predecessor choices cannot select the same undirected edge, again by strict distance decrease. The selected graph is connected and has exactly one edge per nonroot vertex, so is a spanning tree. Along its root paths the distance differences telescope, proving that it is a shortest-path tree even if the original shortest paths were chosen independently.

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.

In a triangle with root $v$, assign $w(va)=w(vb)=2$ and $w(ab)=-1$. Among graph paths, the unique shortest path from $v$ to $a$ is $v,b,a$, and that from $v$ to $b$ is $v,a,b$, both of weight one. A shortest-path tree would have to contain all three edges, impossible for a tree. The example uses shortest simple paths; arbitrary walks can have unboundedly negative weight by repeatedly traversing the negative edge.