Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 7 / d / Solution

Use a dynamic programming state indexed by an edge budget. Put $D_0(s)=0$ and $D_0(v)=\infty$ for $v\ne s$, then for $r=1,\dots ,k$ computeEvery route using at most $r$ edges either already uses at most $r-1$, or ends with some edge $(u,v)$ whose preceding route uses at most $r-1$. Conversely every finite candidate in the displayed equation is attained by such a route. This proves the hop-bounded shortest-route recurrence by induction on $r$, even when weights are negative.

In each round, copy the previous distance row and relax every edge into the new row, always reading from the old row. An in-place pass would allow several new edges in one round and violate the edge budget. Store a predecessor record for every selected candidate, either a carry to $(r-1,v)$ or the incoming edge from $(r-1,u)$. Following records backwards from $(k,t)$ and reversing the collected edges returns the actual optimum route; an infinite final distance means no feasible route exists.

Only vertices incident to an edge, together with $s,t$, need distance fields. In a graph representation whose edges reference vertex records, initialise those fields by visiting both endpoints of every edge, then $s,t$; repeated initialisations are harmless. In each round, first copy old fields to new fields by another complete endpoint pass, and only then begin the relaxation pass. Copying the same endpoint several times before any relaxation also does no harm. Thus each round costs $O(m+1)$, with no scan of isolated vertices, and for $m,k\ge 1$ the total is $O(km)$ time. An implementation that instead initialises full arrays for all vertices has the conventional bound $O(|V|+km)$. For $k=0$ or no edges, only the empty route $s=t$ can succeed.

To realise reconstruction without a dense table, associate a persistent route record with each finite distance. A successful relaxation in round $r$ creates a record containing the new edge and a pointer to the old round's route record at its source; a carry shares its record. All reads use old-round records. At most $km$ such records are created, taking $O(km)$ space, and the returned chain has at most $k$ edges. Distances alone need only two fields per relevant vertex.

Here “route” uses the standard edge-budget shortest-path convention permitting repeated vertices; a bounded budget prevents an arbitrarily long negative-cycle traversal. If “path” instead requires vertex simplicity with unrestricted negative weights, this recurrence does not enforce that extra restriction. With nonnegative weights, removing cycles gives a simple optimum within the same budget.