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.
