Ford Fulkerson Algorithm for Maximum Flow Problem

Ford Fulkerson Algorithm for Maximum Flow Problem


Problem: Given a graph which represents  flow network where every edge has a capacity. Also given two vertices source s and sink t in the graph. Find out the maximum possible flow from s to t with following constraints.

a     i)     Flow on an edge does not exceed the given capacity of the edge.

b     ii)    In-flow is equal to out-flow for every vertex except s and t.

Algorithm:

1      i)   Start with a initial flow as 0.

2      ii)   While there is an augmented path from source to sink ,

     Add this path to the flow

3     iii)    Return flow

Terminologies

i)     Residual graph:  It is a graph which indicates additional possible flow. If there is such path from source to sink then there is a possibility to add flow.

ii)      Residual capacity: original capacity of the edge – flow

iii)      Minimal Cut: Also known as bottleneck capacity which decides maximum possible flow from source to sink through an augmented path.

iv)       Augmenting path: Augmenting path can be two ways:

1)      Non-full forward edges

2)      Non-empty backward edges