<p>P. M. Camerini (1978), The min-max spanning tree problem and some extensions, <em>Information Processing Letters</em> <strong>7</strong> (1): 10–14, doi:<a href="http://dx.doi.org/10.1016/0020-0190%2878%2990030-3">10.1016/0020-0190(78)90030-3</a></p>

CC BY-SA 2.5
2011-02-28T01:54:35.730Z
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.
virgi
CC BY-SA 3.0
2011-05-12T17:02:06.793Z
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.
virgi
CC BY-SA 2.5
2011-03-05T21:55:39.800Z
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
CC BY-SA 2.5
2011-02-28T01:08:40.090Z
2011-02-28T01:08:40.090Z
David Eppstein
<p><a href="http://www.zib.de/Publications/Reports/ZR-06-22.pdf" rel="nofollow">On the Bottleneck Shortest Path Problem</a></p>

CC BY-SA 3.0
2011-05-12T05:10:43.747Z
That one's mostly on the directed version of the problem and it's mostly superceded by an earlier 1988 paper of Gabow and Tarjan  http://www.ams.org/mathscinet-getitem?mr=955149 . See http://en.wikipedia.org/wiki/Widest_path_problem for many more references.
David Eppstein
CC BY-SA 3.0
2017-06-02T05:38:19.810Z
The link is broken.
hengxin
CC BY-SA 3.0
2011-05-12T02:22:48.297Z
2011-05-12T02:22:48.297Z
zenna
<p>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. </p>

<blockquote>
  <p>Does anyone know a reference for
  this?</p>
</blockquote>

CC BY-SA 3.0
2011-05-12T03:39:09.070Z
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.
bbejot
<ds.algorithms><reference-request><graph-algorithms>
Reference for fast algorithm for bottleneck shortest paths
Ben
# Reference for fast algorithm for bottleneck shortest paths

(Asked by: username_0 on 2011-02-27)

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?

**Tags:** ds.algorithms, reference-request, graph-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-02-28. Score: 10

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](http://dx.doi.org/10.1016/0020-0190%2878%2990030-3)

> **Comments:**
> **username_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.  
> **username_0**: 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.  
> **username_3**: 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.  

---

### Answer by username_4 on 2011-05-12. Score: 2

[On the Bottleneck Shortest Path Problem](http://www.zib.de/Publications/Reports/ZR-06-22.pdf)

> **Comments:**
> **username_2**: That one's mostly on the directed version of the problem and it's mostly superceded by an earlier 1988 paper of Gabow and Tarjan  http://www.ams.org/mathscinet-getitem?mr=955149 . See http://en.wikipedia.org/wiki/Widest_path_problem for many more references.  
> **username_5**: The link is broken.  

---

