Facts

• The Ford-Fulkerson method $(G,S,t)$ is iterative
• This method depends on three ideas:
• Augmenting paths
• Residual networks
• Cuts
• Simplified Pseudo-code:
initialize flow f to 0
while there exist an augmenting path p
do augmented flow f along p
return f

Augmenting Paths

• An augmenting path $p$ is a simple path from source $S$ to sing $t$ in the residual network
• Each path have alternative free and matched edges in such way that begins and ends with free vertices.

Residual networks

• Definition: Each edge $(u,v)$ on an augmenting path admits some additional positive flow $u$ to $v$ without violating the capacity constrain on the edge.
• Example:

Cuts

Pseudocode

Ford-Fulkerson $(G,S,t)$
for each edge $(u,v)\epsilon&space;E[G]$
do $f[u,v]\leftarrow&space;0$ // $f$:flow
do $f[v,u]\leftarrow&space;0$
while there exist a path $p$ from $S$ to $t$ in the residual network $Gf$
do $cf(p)\leftarrow&space;min\{cf(u,v):&space;(u,v)$ is in $p&space;\}$ // $cf$: residual capacity
for each edge $(u,v)$ in $p$
do $f[u,v]\leftarrow&space;f[u,v]+cf(p)$ // $p$: path
do $f[v,u]\leftarrow&space;-f[u,v]$

Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is $O(V+E$

Total running time is $O(E|F*|)$ where $f*$ is the maximum flow found

Note: If you find any mistake please let me know