Ford-Fulkerson Algorithm

Initially, the flow of value is 0. Find some augmenting Path p and increase flow f on each edge of p by residual Capacity c_f (p). When no augmenting path exists, flow f is a maximum flow.

FORD-FULKERSON METHOD (G, s, t)   1. Initialize flow f to 0   2. while there exists an augmenting path p   3. do argument flow f along p   4. Return f  

FORD-FULKERSON (G, s, t)   1. for each edge (u, v) ∈ E [G]   2. do f [u, v] ← 0   3. f [u, v] ← 0   4. while there exists a path p from s to t in the residual network Gf.   5. do cf (p)←min?{ Cf (u,v):(u,v)is on p}   6. for each edge (u, v) in p   7. do f [u, v] ← f [u, v] + cf  (p)   8. f [u, v] ←-f[u,v]  

Example: Each Directed Edge is labeled with capacity. Use the Ford-Fulkerson algorithm to find the maximum flow.

Solution: The left side of each part shows the residual network G_f with a shaded augmenting path p,and the right side of each part shows the net flow f.