= 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$, proving
$$
\boxed{\min_{e\in P_T}w(e)=\max_{P:s\leadsto t}\min_{e\in P}w(e).}
$$
This 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)$. Hence
$$
\boxed{\text{time }O(e\log e+v),\qquad\text{auxiliary space }O(e+v).}
$$
For 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.
Back to article page
