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

Start with $(d[1],d[2],d[3],d[4])=(0,\infty ,\infty ,\infty )$. With in-place edge relaxation, the Bellman-Ford algorithm makes the following changes during its first lexicographic pass:The next pass makes no change; any remaining fixed-count passes also make none. Thus the final vector is $(0,4,2,3)$. These are sequential updates within a pass, rather than the simultaneous values of the Synchronous Bellman-Ford recurrence.

Use source $1$, as in the preceding part. The Dijkstra algorithm extracts vertices in the order $1,3,4,2$. Distances after relaxing the outgoing edges of each extracted vertex areThe shortest path to $2$ is $1\to 3\to 4\to 2$, with weight $2+1+1=4$; the direct route to $2$ and the route via $3\to 2$ are both heavier.

Take the directed graph with source $1$ and weighted edgesIt is a Directed acyclic graph, so has no negative-weight graph cycle. The true shortest path to $4$ is $1\to 3\to 2\to 4$, of weight $5-4+1=2$.

The standard label-setting shortest-path algorithm version of the Dijkstra algorithm extracts $1$, then $2$ at distance $2$, then $4$ at distance $3$, and only then $3$ at distance $5$. Thus it finalises $d[4]=3$ instead of $2$. Even if an implementation subsequently changes the stored label of the already settled vertex $2$, it does not reprocess its outgoing edge to $4$, so the error at $4$ remains. Allowing repeated reprocessing would instead be a label-correcting shortest-path algorithm, not the usual Dijkstra guarantee.

First run breadth-first search, ignoring weights, to obtain the minimum number of edges $h(v)$ from the source to each reachable vertex. Then compute weighted distances only along edges that advance one breadth-first layer:Unreachable vertices keep distance $\infty$. For an undirected graph, scan both orientations of each edge.

To justify discarding other routes, a shortest path can be taken simple because every weight is positive. A simple path of $r\le n-1$ edges has weight inEvery path with at least $r+1$ edges weighs at least $r+1$. Consequently every minimum-weight path must also have the minimum possible number of edges: this is minimum-hop dominance for nearly unit weights.

A minimum-hop path to $v$ uses exactly $h(v)$ edges. Every prefix of such a path must itself have minimum hop count, since replacing a longer prefix by a shorter one would shorten the whole route. Hence it advances from layer $j$ to layer $j+1$ at every step. The retained edges form a Directed acyclic graph, ordered by $h$. The displayed dynamic programming recurrence therefore finds the cheapest of all minimum-hop paths, which by the preceding bound is a true shortest path.

With an adjacency list, both the breadth-first search and the layer-ordered relaxations take $O(n+m)$ time and $O(n+m)$ total storage, where $m=|E|$. The queue order from breadth-first search already supplies the layer order; no sorting or priority queue is needed. This improves the usual $O((n+m)\log n)$ binary-heap Dijkstra bound and is linear in the input size.