Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8

Initialize $d[s]=0$ and $d[v]=\infty$ elsewhere. Perform $|V|-1$ full passes over the directed edges, applying edge relaxation $d[v]\leftarrow \min \{d[v],d[u]+w(u,v)\}$ whenever $d[u]$ is finite. For an undirected graph, process each edge in both directions. Stop early if a pass makes no change.

Each finite label records the cost of a discovered directed walk, so it never understates the true infimum. After $t$ passes, relaxation has propagated along every route of at most $t$ edges, so the label is no greater than the cost of any such route. If no reachable negative-cost closed walk exists, an optimal route can be chosen without repeated vertices and has at most $|V|-1$ edges. These inequalities prove that the final labels are the desired shortest path lengths.

An additional pass checks for an improving edge from a reachable vertex. If one exists, report a reachable negative-cost cycle: finite shortest distances cannot be assigned to vertices reachable from that cycle. Mark those vertices by forward reachability if individual $-\infty$ answers are wanted. In particular, a reachable negative undirected edge becomes a negative two-arc closed walk under the bidirected interpretation; generic signed weights do not guarantee finite answers.

Each pass costs $O(|E|)$, giving $O(|V||E|)$ for the usual Bellman-Ford algorithm bound. Including initialization gives $O(|V|+|V||E|)$, which also handles an edgeless graph honestly; these coincide in order when $|E|\ge 1$.

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.

Find a topological sorting of the Directed acyclic graph. Initialize $L[s]=0$ and $L[v]=-\infty$ for $v\ne s$. Process vertices in that order. At a reachable vertex $u$, update each outgoing edge by $L[v]\leftarrow \max \{L[v],L[u]+w(u,v)\}$, and retain a predecessor whenever an improvement is made.

Every path to a vertex ends at an earlier vertex in the topological sorting. Thus, when $v$ is processed, all possible final-edge candidates for $v$ have already been considered. Induction along the order proves that $L[v]$ is the longest path length from $s$, with $-\infty$ exactly for unreachable vertices. Signed weights cause no problem because the graph has no directed cycle. The running time is $O(|V|+|E|)$, and predecessor pointers recover a maximizing path.

Permit every vertex to start a path: initialize $L[v]=0$ for all $v$, then perform the same maximum-relaxation pass in topological sorting order. Equivalently, the recurrence isThe zero option starts a fresh, zero-edge path; the other options extend an optimal path ending at a predecessor. The largest final entry is therefore the longest path length in the graph, allowing a zero-edge path. This takes $O(|V|+|E|)$, which is $O(|V{|}^2)$ for the ordinary simple-graph representation.

If at least one edge is required, keep the same prefix values but return ${\max }_{(u,v)\in E}(L[u]+w(u,v))$ instead of ${\max }_{v}L[v]$. That variant correctly returns a negative optimum when all nonempty paths have negative weight, and reports no nonempty path if the edge set is empty. No all-pairs repetition is needed.

Sort the two dimension vectors separately into ascending order, $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$. Then return true exactly when $a_i<b_i$ for every $i$. Sorting costs $O(d\log d)$ and the coordinate comparisons cost $O(d)$.

Sufficiency follows by matching corresponding ranks and translating that rank matching back to the original axes. For necessity, suppose $a_k\ge b_k$ for some $k$. The $d-k+1$ dimensions $a_k,\dots ,a_d$ must all be assigned to strictly larger target dimensions. None of the first $k$ sorted target dimensions is large enough, leaving at most $d-k$ eligible slots. The pigeonhole principle gives a contradiction. This proves the sorted-coordinate criterion for box containment, including ties: equality fails the required strict fit.

Read “subsequence” in its usual sense: selected indices increase in the given input order. First sort each box's dimension vector, in $O(nd\log d)$ total time. Let $F[j]$ be the maximum number of boxes in a fitting subsequence ending at index $j$. Process $j=1,\dots ,n$ and computeThe last selected box before $j$, if any, supplies exactly one of these candidates; conversely an optimal candidate subsequence can be extended by $j$. Induction on $j$ proves the box nesting recurrence. Store a maximizing predecessor index and reconstruct from an index maximizing $F[j]$. For $n=0$, return the empty subsequence.

There are $O(n^2)$ candidate pairs, each requiring $O(d)$ coordinate comparisons. Hence $O(nd\log d+n^{2}d)$ running time and $O(nd+n)$ storage suffice, including sorted vectors, table entries and reconstruction pointers. It is unnecessary to store every fitting pair.

If “subsequence” was intended to allow arbitrary reordering, build the containment Directed acyclic graph instead: include every fitting ordered pair, then find its longest chain. Strict increase of the smallest sorted dimension gives a topological sorting by that dimension. The same pair-testing bound applies, but the index restriction must then be removed. These two interpretations differ: input boxes $(3,3),(2,2)$ have a longest order-preserving subsequence of one box, but an unrestricted nesting chain of two.