= Bottleneck shortest path problem
{title2=$\min_{P:x\leadsto y}\max_{e\in E(P)}\ell(e)$}
Unlike the sum in the usual <shortest path problem>, the bottleneck cost of a nonempty <graph path> is its largest <edge> weight. The optimum is the smallest threshold at which the endpoints become connected by edges of weight at most that threshold. Sorting edges and increasing the threshold, with a <disjoint-set data structure> maintaining components, finds this value. The <minimax path property of a minimum spanning tree> provides a single tree representing such optimal routes for every pair of vertices.
Back to article page
