The Edmonds$-$Karp algorithm implements the Ford$-$Fulkerson algorithm by always

choosing a shortest augmenting path in the residual network. Suppose instead that the Ford$-$

Fulkerson algorithm chooses a widest augmenting path: an augmenting path with the greatest

$1$

residual capacity. Assume that G $=($V$,$ E$)$ is a flow network with source s and sink t$,$ that

all capacities are integer, and that the largest capacity is C$.$ In this problem, you will show

that choosing a widest augmenting path results in at most $$E$$ ln $$f$$ augmentations to find a

maximum flow f$.$

a$.$ Show how to adjust Dijkstra$$s algorithm to find the widest augmenting path in the residual

network.

b$.$ Show that a maximum flow in G can be formed by successive flow augmentations along at

most $$E$$ paths from s to t$.$

c$.$ Given a flow f$,$ argue that the residual network Gf has an augmenting path p with residual

capacity cf $($p$)($f$$f$)/$E$.$

d$.$ Assuming that each augmenting path is a widest augmenting path, let fi be the flow after

augmenting the flow by the ith augmenting path, where f$0$ has f$($u$,$ v$)=0$ for all edges

$($u$,$ v$).$ Show that $$f$$fi$$f$(11/$E$)$i$.$

e$.$ Show that $$f$$fi$<$f$$e$$i$/$E$.$ You may want to use inequality $(3\mathrm{.}14)$ from the text,

$1+$ x