# Reference for fast algorithm for bottleneck shortest paths

I am looking for a good reference for bottleneck shortest paths. Specifically, given vertices s and t in an undirected graph with edge weights, you want the shortest path from s to t, where the length of a path is the maximum edge on that path. This can be solved in O(n+m) time by finding the median edge weight and (carefully) recursively deleting half the edges.

Does anyone know a reference for this?

• Perhaps this is a moot point, but the problem you describe is the minimax path problem. Bottleneck shortest path is the max-min version of what you describe. An algorithm for one of the version generally (always?) yields an algorithm for the other version however. May 12, 2011 at 3:39

## 2 Answers

P. M. Camerini (1978), The min-max spanning tree problem and some extensions, Information Processing Letters 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3

• Btw, if you want to solve the single-source (and in a sense the all-pairs) version of the problem for undirected graphs, you can do it in randomized O(m+n) time: T.C. Hu noted in 1961 that the bottleneck paths for all pairs are encoded in a max spanning tree; then Karger,Klein and Tarjan's linear time min spanning tree algorithm gives you what you want. Feb 28, 2011 at 1:54
• As far as I can tell the reference is not what I need. An st path in a min-max spanning tree is not necessaryily a bottleneck shortest st path. Also, the KKT linear expected time algorithm is not what I need either, since I want deterministic not expected running time. Thanks anyway for the help though.
– Ben
Mar 5, 2011 at 21:55
• Actually, the st path P in a minimum spanning tree T has a minimum maximum edge weight over all st paths. Suppose it doesn't. Then let the max edge of P be e. Removing e from T creates a cut of the graph. The real minmax st path P' must have an edge e' crossing this cut. Adding e' to T\{e} creates a new spanning tree T' which must have a smaller cost than T since the weight of e' is at most the max edge weight on P' which is less than w(e). This contradicts the fact that T is a min spanning tree. May 12, 2011 at 17:02