<p>Given a directed graph G and vertices s and t, the maximum capacity path between s and t is the path for which the minimum edge on the path is maximum, among all such s-t paths. Now I can use a modified Dijkstra's single-source shortest path algorithm to find a single maximum capacity path. But suppose, among all such maximum capacity paths, I want the one with the maximum capacity between all pairs of vertices on the path. Does anyone know a reference for this? I use the following modification of Dijkstra's:</p>

<pre><code>ModifiedDijkstra(G,s)   
for all v in G  
    d(v) -&gt; -1  
    pred(v) -&gt; null  

d(s)-&gt; infinity  
Q -&gt; V[G] // enqueue all the vertices in G.  

while Q is not empty  
    u-&gt;EXTRACT_MAX(Q)  
    for each v in Adj(u)  
        if d(v)&lt;min(c(u,v),d(u))        // d(v)=max(d(v),min(d(u),c(u,v)))    
            d(v)=min(c(u,v),d(u))  
            pred(v)=u  
</code></pre>

<p>Note that the answer I am looking for is a specific maximum capacity path (of many). For example for the directed graph G=({a,b,c,d,e},{(a,b),(b,c),(a,c),(c,d),(c,e),(d,e)}) with capacities c(a,b)=10,c(b,c)=10,c(a,c)=5,c(c,d)=20,c(c,e)=11,c(d,e)=15. Maximum capacity paths from a to e can be abce or abcde but I need abcde as answer as it is fattest from c to e, i.e. maximum capacity from c to e on abcde is 15 as opposed to 11 on abce. </p>

<p>Update: In practice all my edge weights are floating point numbers and guaranteed to be unique (say). In that case, once I find a single max capacity path, I will fix the minimum weight edge (say (u,v)), and recurse to find the max capacity path over the 2 subraphs, s...u and v....t. I will have to do this a maximum of E times so the time complexity of such an algorithm would be O(V^2E): with a naive implementation of Dijkstra's. </p>

CC BY-SA 3.0
2013-02-01T00:53:28.173Z
motivation for the problem is to compute reaction flux in computer simulations of biological processes.
shruvis
CC BY-SA 3.0
2013-02-01T05:01:58.267Z
Isn't this question the same as [this](http://cstheory.stackexchange.com/q/16175/)?
Kaveh
CC BY-SA 3.0
2013-02-01T07:20:36.913Z
@Kaveh: As I understand it, the question you linked to is the “find a single maximum capacity path” part of the current question (which the OP knows how to do).  I think that the OP is asking about something else, although I cannot understand what it is.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-01T07:22:31.977Z
Not quite the same, because of the tie-breaking rule. (Though it's not clear to me that the rule is well-defined.)
David Eppstein
CC BY-SA 3.0
2013-02-01T08:59:01.917Z
thanks. No it is not the same as max capacity/max flux path. Added an example to the question to clarify the difference. The ties between multiple max capacity paths are the problem, and what I am seeking to break.
shruvis
CC BY-SA 3.0
2013-02-01T10:41:55.290Z
I cannot follow what you are using to pick one among multiple max-capacity paths. For example, consider a graph with edge capacities $w(a,b)=1$, $w(b,c)=4$, $w(c,e)=4$, $w(a,d)=1$, $w(d,e)=4$. Which among the paths $a,b,c,e$ and $a,d,e$ will you choose?
polkjh
CC BY-SA 3.0
2013-02-01T18:27:39.583Z
In this case, both are equally good, but if the graph is w(a,b)=1,w(a,c)=1, w(c,d)=4,w(b,d)=5, I would need abd not abc. Is this perhaps ill-defined?
shruvis
CC BY-SA 3.0
2013-02-02T05:19:40.960Z
In the absence of a precise definition of the proposed tie-breaking rule, I am voting to close as "not a real question".  Can you provide an _algorithm_ to determine which of two paths is "fatter", instead of just an example?
Jeffε
CC BY-SA 3.0
2013-02-04T03:29:52.343Z
The maximum capacity path should be such that for all pairs of vertices v1, v2, on the path, the subpath from v1 to v2 is the maximum capacity path between these 2 vertices. I imagine that this can be done if all edge weights are unique (see update to question above). But not sure a solution exists if there are multiple edges with same weight. Thanks.
shruvis
<ds.algorithms><reference-request><graph-algorithms>
Widest path between s and t with additional constraints
shruvis
# Widest path between s and t with additional constraints

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

Given a directed graph G and vertices s and t, the maximum capacity path between s and t is the path for which the minimum edge on the path is maximum, among all such s-t paths. Now I can use a modified Dijkstra's single-source shortest path algorithm to find a single maximum capacity path. But suppose, among all such maximum capacity paths, I want the one with the maximum capacity between all pairs of vertices on the path. Does anyone know a reference for this? I use the following modification of Dijkstra's:
ModifiedDijkstra(G,s)   
for all v in G  
    d(v) -> -1  
    pred(v) -> null  

d(s)-> infinity  
Q -> V[G] // enqueue all the vertices in G.  

while Q is not empty  
    u->EXTRACT_MAX(Q)  
    for each v in Adj(u)  
        if d(v)
Note that the answer I am looking for is a specific maximum capacity path (of many). For example for the directed graph G=({a,b,c,d,e},{(a,b),(b,c),(a,c),(c,d),(c,e),(d,e)}) with capacities c(a,b)=10,c(b,c)=10,c(a,c)=5,c(c,d)=20,c(c,e)=11,c(d,e)=15. Maximum capacity paths from a to e can be abce or abcde but I need abcde as answer as it is fattest from c to e, i.e. maximum capacity from c to e on abcde is 15 as opposed to 11 on abce. 
Update: In practice all my edge weights are floating point numbers and guaranteed to be unique (say). In that case, once I find a single max capacity path, I will fix the minimum weight edge (say (u,v)), and recurse to find the max capacity path over the 2 subraphs, s...u and v....t. I will have to do this a maximum of E times so the time complexity of such an algorithm would be O(V^2E): with a naive implementation of Dijkstra's.

**Tags:** ds.algorithms, reference-request, graph-algorithms
> **Comments:**
> **username_0**: motivation for the problem is to compute reaction flux in computer simulations of biological processes.  
> **username_1**: Isn't this question the same as [this](http://cstheory.stackexchange.com/q/16175/)?  
> **username_2**: @Kaveh: As I understand it, the question you linked to is the “find a single maximum capacity path” part of the current question (which the OP knows how to do).  I think that the OP is asking about something else, although I cannot understand what it is.  
> **username_3**: Not quite the same, because of the tie-breaking rule. (Though it's not clear to me that the rule is well-defined.)  
> **username_0**: thanks. No it is not the same as max capacity/max flux path. Added an example to the question to clarify the difference. The ties between multiple max capacity paths are the problem, and what I am seeking to break.  
> **username_4**: I cannot follow what you are using to pick one among multiple max-capacity paths. For example, consider a graph with edge capacities $w(a,b)=1$, $w(b,c)=4$, $w(c,e)=4$, $w(a,d)=1$, $w(d,e)=4$. Which among the paths $a,b,c,e$ and $a,d,e$ will you choose?  
> **username_0**: In this case, both are equally good, but if the graph is w(a,b)=1,w(a,c)=1, w(c,d)=4,w(b,d)=5, I would need abd not abc. Is this perhaps ill-defined?  
> **username_5**: In the absence of a precise definition of the proposed tie-breaking rule, I am voting to close as "not a real question".  Can you provide an _algorithm_ to determine which of two paths is "fatter", instead of just an example?  
> **username_0**: The maximum capacity path should be such that for all pairs of vertices v1, v2, on the path, the subpath from v1 to v2 is the maximum capacity path between these 2 vertices. I imagine that this can be done if all edge weights are unique (see update to question above). But not sure a solution exists if there are multiple edges with same weight. Thanks.  

---

## 0 answers

