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

The Dijkstra algorithm finalises vertices in the order $1,3,2,5,4$. After finalising $1$, tentative distances to $2,3$ are $3,2$. Finalising $3$ sets the distance to $5$ to $4$. Finalising $2$ sets the distance to $4$ to $6$. Finalising $5$ improves the distance to $4$ to $5$; its edge to $2$ proposes $5$ and causes no improvement. The final distance vector in vertex order is $(0,3,2,5,4)$. All weights are positive, so every finalisation is justified by the usual label-setting shortest-path algorithm invariant. The method is named for Edsger W. Dijkstra.

The intermediate states of the Bellman-Ford algorithm depend on edge order. Specify in-place edge relaxation in lexicographic directed-edge order:Starting with $(0,\infty ,\infty ,\infty ,\infty )$, the first pass changes the vector as follows; omitted relaxations make no change:The next pass makes no change, allowing early termination. If all $|V|-1=4$ passes are performed, passes two through four retain $(0,3,2,5,4)$.

For the synchronous convention, where every relaxation reads only the previous row, the Synchronous Bellman-Ford recurrence instead givesBoth conventions reach the same shortest distances. The algorithm's eponyms are Richard Bellman and L. R. Ford Jr..

Let $N=|V|$ and replace every edge weight by $w^{\prime }(e)=Nw(e)+1$. Call the supplied shortest-path routine once using these new weights, and return its path in the original graph. For every path $P$,where $|P|$ is its number of edges. Positive original weights imply positive transformed weights, so a shortest route can be taken to be simple and has at most $N-1$ edges. Distinct integral original weights of paths differ by at least one. Thus if $w(P)<w(Q)$ for simple paths, thenFor equal original weights, the transformed comparison is exactly the comparison of hop counts. Therefore every transformed shortest path minimises original weight first and number of edges second, proving the integer-weight shortest-path tie-breaking lemma. The transformation costs $O(N+|E|)$ time, followed by one subroutine call. Weights gain only $O(\log N)$ bits; exact arithmetic should be used if multiplying machine-sized weights might overflow. If $t$ is unreachable, it remains unreachable.

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.