Minimum bottleneck path between two vertices in an undirected graph
I will use the fact that you can check for the connectivity between two vertices $s$ and $t$ in a graph with $m&gt;0$ edges in time $O(m)$.

Call $G$ be the input graph, and let $s$ and $t$ be endpoints of the paths you are interested in. I will denote by $G_w$ (resp. $G^&lt;_w$) the graph induced by all the edges of weight at most (resp. less than) $w$ in $G$. You can solve the problem using the following recursive algorithm:

If $G$ has no edges, report that $s$ and $t$ are disconnected in $G$.

If $G$ has at least one edge, find the median $w$ among the edge weights of $G$, and proceed as follows:


If  $s$ and $t$ are connected in $G_w$ and disconnected in $G^&lt;_w$, return $w$.
If $s$ and $t$ are connected in both $G_w$ and $G^&lt;_w$, apply the algorithm recursively on $G^&lt;_w$ (notice that $G^&lt;_w$ has at most $\frac{m}{2}$ edges).
If $s$ and $t$ are disconnected in $G_w$, build the graph $G'$ obtained from $G$ by
identifying all vertices that belong to the same connected component of $G_w$, and apply the algorithm recursively on $G'$ (notice that $G'$ has at most $\frac{m}{2}$ edges, since it can't contain any edge with weight less than or equal to $w$).


The time complexity of the above algorithm is described by the recurrence equation:
$T(m) = T(m/2) + O(m)$, which has solution $T(m)=O(m)$.

This problem is the same as its maximization version once all edge weights are multiplied by $-1$.