Max flow problem

The max flow problem can be defined as “Given a flow network as directed graph, where each edge has a capacity greater than 0 and two distinct nodes source S and sink T, find the maximum flow from source node S to sink node T.”

The condition with problem is
(1) Flow on each edge cannot exceed by its capacity.
(2) For every node the incoming  flow is equal to outgoing flow, except source node s and sink node t.

A flow that satisfies the above condition is called a feasible flow. The edge of the graph can be seen as pipelines or roads and nodes can be seen as junction. For example let us see below graph. The edge weight of the graph is flow capacity.
Max flow problem Ford Fulkerson algorithmThe Ford-Fulkerson algorithm determines the maximum flow of the network from source to sink node.
Augmenting Path:

An Augmenting Path is simple path from source node to sink node ( without cycle ) , where we can send a positive flow along the path from source node to sink node. For example in above example graph , we can send a positive flow along the augmenting path 5 0 1 6.

Residual Graph:

After sending a positive flow along an augmenting path, the flow capacities of edges are being adjusted , these adjusted flow capacities are called residual capacities and the resulting graph/network is called residual graph/network.

Ford-Fulkerson Algorithm
1) Start with initial flow as 0.
2) While there is a augmenting path from source to sink.
Find the min flowcapacity
Adjust the graph.
Add this min flow to the flow

3) Return flow.

Here is steps for max flow on example graph  using Ford-Fulkerson method.

Step ( 1)

Find a augmenting path from Source S to sink T.  ( 5 –> 0 -> 1 -> 6 )

Choose minimum capacity : 4 , say it f1 = 4 . Adjust the capacity of each path. Now we can see that along this augmenting path we can send maximum flow of capacity 4.

Max flow problem Ford Fulkerson algorithm step 1

Step ( 2)

Find a another augmenting path from Source S to sink T. (Let it is , 5 –> 0–> 2–>6 )

find min capacity along this path : 2. Adjust the capacities of each edge. We can send max flow along this path is 2. f2 = 2.

Max flow problem Ford Fulkerson algorithm step 3

Step ( 3)

Find a another augmenting path from Source S to sink T. (Let it is , 5 –> 3-> 4–>6)

find min capacity along this path : 2. f3 = 2, Adjust the capacities of each edge.

Max flow problem Ford Fulkerson algorithm step 4

Now there is no augmenting path from source to sink. Hence total max flow capacity is f = f1 + f2 + f3 = 4 + 2 + 2 = 8.

Here is sample implementation in c++.  For searching augmenting path from source to sink node depth first search has been used in the c++ implementation.

Ref:
https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm