Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

For directed graph $(G=(V, E),s,t,{Ce})$ in which we want to maximize max flow. All edge capacities are at least one. Define the capacity of an $s \to t$ path to be the smallest capacities of constituent edges. The fastest path from $s$ to $t$ is the path with the most capcity.

b) Show that the fastest path from $s$ to $t$ in a graph can be computed by Dijkstra's algorithm.

c) Show that the maximum flow in $G$ is the sum of individual flows along at most $|E|$ paths from $s$ to $t$.

It's one of the questions from my algorithms assignment, and I figured out (a), but can't get these two above.

share|improve this question
2  
Cross posted at math.stackexchange.com/questions/233770/…. At least link the two questions. Better: don't do that. –  A.Schulz Nov 9 '12 at 20:55
add comment

1 Answer

For b), you can construct a graph $G' = (V, E)$ where $e \in E$ has weight the inverse of the capacity of the corresponding edge in $G$. You can then easily prove that a shortest path in $G'$ (where the weight of a path is defined inductively as $w(u_1, \dots, u_n, u_{n+1}) = max(w(u_1, \dots, u_n), w(u_{n+1})) = max(w(u_1), \dots, w(u_{n+1}))$) is a path with maximum capacity in $G$. For c), you can use the fact that if you have $|E|$ paths in $G$, then at least two of them share an edge.

share|improve this answer
    
Why was my answer downvoted ? –  beauby Nov 11 '12 at 5:42
    
How do you make Dijkstra's algorithm work with that funny weight function? It's not a weight function on edges; it's a function on paths. As far as I remember, Dijkstra's algorithm only works if you put weights on edges. –  Peter Shor Nov 11 '12 at 17:45
    
I made a mistake while writing my answer (replaced a max with a min, sorry). However, if you take the proof of Dijkstra's algorithm, and just replace the distance function with the one above, everything works exactly the same way. –  beauby Nov 11 '12 at 17:54
    
Ok, I think I was not very clear in my answer. The weights are on the edges, but the only difference is that along a path, the weights are not combined with the + operator, but with the max operator. (and it is very true that my answer was incomplete when you downvoted it). –  beauby Nov 11 '12 at 17:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.