Maximum-flow: Ford-Fulkerson algorithm

Maximum-flow: Ford-Fulkerson algorithm

Initially set all weights in the flow graph to 0. Then:

1. Compute the edge weights in the residual graph Gr from the current flow graph Gf :

• For each edge (u,v,c) in G, and corresponding edge (u,v,f) in Gf , do the following:
• Update forward edge (u,v,x) in Gr to be (u,v, c-f)
• If f>0, create or update backward edge (v,u,x) in Gr to be (v,u, f)
• Consider 0-weight edges in the resulting Gr as nonexistant.
  

2. Find the s-t augmenting path P in Gr with largest bottleneck edge weight b. If there is no s-t path in Gr , Done: Gf shows the maximum flow.

3. Update the flow graph Gf with the flow along the augmenting path P:

• For each edge (u,v,x) in P, update edge weights in the flow graph Gf :
• If (u,v) is a forward edge in Gr , update edge (u,v,f) in Gf to be (u,v, f+b).
• If (u,v) is a backward edge in Gr , update edge (v,u,f) in Gf to be (v,u, f-b).
  

4. Go to 1.

Read full article from Maximum-flow: Ford-Fulkerson algorithm