 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. For a finite undirected graph, sorting edges and increasing the threshold, with a disjoint-set data structure maintaining components, finds this value. In the same undirected setting, the minimax path property of a minimum spanning tree provides a single tree representing such optimal routes for every pair of vertices.