Category: Algorithms

Facts

• The Ford-Fulkerson method  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 is a simple path from source to sing 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 on an augmenting path admits some additional positive flow  to  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:
  Net-flow Across Cut (including net-flow between vertices):
  Capacity (only edges going from source to sink ):

Pseudocode

// Comments
Ford-Fulkerson
for each edge
do // :flow
do
while there exist a path from to in the residual network
do is in // : residual capacity
for each edge in
do // : path
do

Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is

Total running time is where is the maximum flow found

Note: If you find any mistake please let me know