# Dijskstra's algorithm, maximum flow

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.

-
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

## 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.

-
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