1
$\begingroup$

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)<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

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ motivation for the problem is to compute reaction flux in computer simulations of biological processes. $\endgroup$ – shruvis Feb 1 '13 at 0:53
  • $\begingroup$ Isn't this question the same as this? $\endgroup$ – Kaveh Feb 1 '13 at 5:01
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Feb 1 '13 at 7:20
  • 1
    $\begingroup$ 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? $\endgroup$ – polkjh Feb 1 '13 at 10:41
  • 1
    $\begingroup$ 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? $\endgroup$ – Jeffε Feb 2 '13 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.