Ford-Fulkerson Method

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

Minimum cut of a network: A cut whose capacity is minimum over all cuts on the network.
Max-flow min-cut theorem: A flow is maximum if and only if its residual network contains no augmenting path.
Example: $cut(\{S, v_{1}, v_{2}\}), \{v_{3}, v_{4}, t\})$
Net-flow Across Cut (including net-flow between vertices): $f(v_{1}, v_{3}) + f(v_{2},v_{3}) + f(v_{2}, v_{4}) = 14 + (-4) + 11 = 19$
Capacity (only edges going from source $S$ to sink $t$ ): $c(v_{1}, v_{3}) + c(v_{2}, v_{4}) = 12 + 14 = 26$

Pseudocode

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