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
