<p>The problem is known as "<a href="http://en.wikipedia.org/wiki/Widest_path_problem">Maximum capacity path problem</a>" or  "Widest path problem"</p>

<p>See the original paper: <a href="http://www.jstor.org/discover/10.2307/167055?uid=3738296&amp;uid=2129&amp;uid=2&amp;uid=70&amp;uid=4&amp;sid=21101691403027">T. C. Hu, "The Maximum Capacity Route Problem", Operations Research Vol. 9, No. 6 (Nov. - Dec., 1961), pp. 898-900</a></p>

<p>or the linear time algorithm described in: <a href="http://www.sciencedirect.com/science/article/pii/0377221791900735">A. P. Punnen, "A linear time algorithm for the maximum capacity path problem</a>" (but I didn't download/read it)</p>

CC BY-SA 3.0
2013-01-22T13:15:44.160Z
2013-01-22T13:15:44.160Z
Marzio De Biasi
<p>Given a graph $G$ and two vertices $s$ and $t$, I want the maximum flux path from $s$ to $t$.That is, imagine $G$ to be a flow network with capacities on the edges. I want to find a single path that can carry the maximum flow between $s$ and $t$.</p>

<p>Note that this is not the same as the maximum flow problem where you can compute flows from multiple paths. </p>

<p>Can someone point me to fast algorithms for computing the max flux path? </p>

CC BY-SA 3.0
2013-01-22T02:54:44.480Z
i.e. you want a path P from A to B with the least-weight edge in P having maximum possible value.
Kaveh
CC BY-SA 3.0
2013-01-28T05:53:15.693Z
This is a standard undergraduate homework exercise.
Jeffε
CC BY-SA 3.0
2013-01-29T06:29:45.983Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
<ds.algorithms><reference-request><graph-algorithms>
Find the maximum flux path between two nodes
shruvis
# Find the maximum flux path between two nodes

(Asked by: username_0 on 2013-01-22)

Given a graph $G$ and two vertices $s$ and $t$, I want the maximum flux path from $s$ to $t$.That is, imagine $G$ to be a flow network with capacities on the edges. I want to find a single path that can carry the maximum flow between $s$ and $t$.

Note that this is not the same as the maximum flow problem where you can compute flows from multiple paths.

Can someone point me to fast algorithms for computing the max flux path?

**Tags:** ds.algorithms, reference-request, graph-algorithms
> **Comments:**
> **username_1**: i.e. you want a path P from A to B with the least-weight edge in P having maximum possible value.  
> **username_2**: This is a standard undergraduate homework exercise.  
> **username_1**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_3 on 2013-01-22. Score: 6

The problem is known as "[Maximum capacity path problem](http://en.wikipedia.org/wiki/Widest_path_problem)" or "Widest path problem"

See the original paper: [T. C. Hu, "The Maximum Capacity Route Problem", Operations Research Vol. 9, No. 6 (Nov. - Dec., 1961), pp. 898-900](http://www.jstor.org/discover/10.2307/167055?uid=3738296&uid=2129&uid=2&uid=70&uid=4&sid=21101691403027)

or the linear time algorithm described in: [A. P. Punnen, "A linear time algorithm for the maximum capacity path problem](http://www.sciencedirect.com/science/article/pii/0377221791900735)" (but I didn't download/read it)


---

