Dijskstra's algorithm, maximum flow

Question

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.

Answer 1

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.