 Bottleneck shortest path problem

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.