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

Dijkstra's algorithm solves the single-source shortest-path problem with nonnegative edge weights: it finds minimum path lengths from the source to all reachable vertices and can store predecessor edges. With adjacency lists and a binary-heap priority queue, it takes $O((|V|+|E|)\log |V|)$ time; a direct array implementation takes $O(|V{|}^2)$.

The Bellman-Ford algorithm allows negative edge weights. If no negative-weight cycle is reachable from the source, it computes the finite shortest-path distances to reachable vertices and identifies unreachable ones. Otherwise it can report a reachable negative cycle, whose repeated traversal makes distances to some reachable vertices unbounded below. It performs at most $|V|-1$ full relaxation rounds and one further detection round, taking $O(|V||E|+|V|)$ time, conventionally written $O(|V||E|)$ for nontrivial edge sets. A negative cycle unreachable from the source does not affect its distance problem.

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.

No. For a path $P$ with $k$ edges, adding $C$ to every edge changes its cost toDifferent paths can have different numbers of edges, so this transformation need not preserve their order.

For a concrete Directed acyclic graph, use edges $s\to t$ of weight $1$, $s\to u$ of weight $-2$, and $u\to t$ of weight $2$. Originally the route through $u$ has cost $0$ and beats the direct edge of cost $1$. Adding $C=3$ makes every edge positive, but the direct route now costs $4$, while the route through $u$ costs $1+5=6$. Dijkstra's algorithm on the modified graph therefore returns a path that is not shortest in the original graph.

The two-edge path receives the added constant twice; the direct path receives it once. This is the failure of uniform edge shifts to preserve shortest paths.

A topological sort of a Directed acyclic graph is a linear ordering of its vertices in which the tail of every directed edge precedes its head. Along a path $v_0\to v_1\to \cdots \to v_k$, this property successively givesin that ordering. Thus the vertices of every directed path occur in topological order. The acyclicity condition is necessary, since a directed cycle would force its first vertex to precede itself.

Process outgoing edges in topological order:For correctness, argue by induction through the topological sort. Every path ending at a vertex $v\ne s$ reaches it through some incoming edge $uv$. All such predecessors $u$ occur earlier, so their finalized shortest-path distances have already been considered when $v$ is processed. Taking the minimum of $\mathrm{distance}(u)+w(u,v)$ over these edges therefore gives exactly the shortest-path distance to $v$. Unreachable vertices retain infinity. Negative edge weights cause no difficulty because a later vertex cannot lead back to an earlier one.

This is the DAG shortest-path algorithm. Topological sorting and the single pass of edge relaxation each take $O(|V|+|E|)$ time with adjacency lists; distances, predecessors and the order use $O(|V|)$ auxiliary space. Following predecessors reconstructs a shortest path to any reachable target.