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

Build a maximum spanning tree $T$ by the decreasing-weight version of Kruskal's algorithm. For the specified distinct endpoints $s,t$, find their unique graph path $P_T$ in $T$ by depth-first search, retaining predecessors to reconstruct it. Return that path and its minimum edge weight $b$.

For correctness, choose an edge $e$ of weight $b$ on $P_T$. Deleting it splits $T$ into two connected components, separating $s$ from $t$. No edge $f$ across this cut of a graph can have $w(f)>b$: replacing $e$ by $f$ would give a spanning tree of greater total weight, contradicting maximality of $T$.

Every $s$–$t$ graph path $P$ must cross the same cut of a graph, so it contains a crossing edge $f$ with $w(f)\le b$. Therefore its minimum edge weight is at most $b$. The tree route attains $b$, provingThis is precisely the widest path problem. The proof allows tied, zero and negative edge weights. It depends on maximizing the total tree weight, not on a shortest-distance algorithm.

Let $v=|V|$ and $e=|E|$. Sorting and Kruskal's algorithm take $O(e\log e+v)$ time; the tree search adds $O(v)$. HenceFor a connected simple graph with at least two vertices, $v-1\le e\le v(v-1)/2$, so the time is also $O(e\log v)$. The $O(e\log e+v)$ expression remains valid when parallel edges are permitted. If the two endpoints coincide, the empty path is returned, with bottleneck $+\infty$ under the usual empty-minimum convention; otherwise connectedness guarantees a nonempty route.