**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

- 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.

- 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*