Introduction💁
The max flow problem is a very important problem that is used to find the maximum flow a network can carry. The max flow problem is often used to solve the problems associated with complex networks. A common problem that can be solved using the max flow problem is the circulation problem. The initial vertex in the max flow problem is known as the “source.” The final vertex is known as the “sink.” Each edge has a “limit.” The limit is the value that can be further carried by the vertice.
Example📝
Let us consider a graph and understand what actually is the max flow problem.
In the above example, the maximum flow that can be carried in the graph is 10.
In this example source is 0, and the sink is 5.
First Path: 0->2->3->5 (Min Capacity = 5)
Second Path: 0->2->4->5 (Min Capacity = 10)
Third Path: 0->1->2->4->5 (Min Capacity = 1)
Fourth Path: 0->1->2->3->5 (Min Capacity = 1)
So the maximum capacity out of the four paths is 10. Thus the maximum flow for the given graph is 10.
Algorithm
Number of Edges: (N)
Flow of Edge: F(n) (Capacity of each edge)
Capacity of Edge: C(n) (Current Capacity)
Step 1: Initialise the F(n) as 0 for each value of n, assign the max_value as 0
Step 2: Repeat the following steps for path P from s to t, where s is the source node, and t is the end node.
- The path exists if F(n) is less than or equal to C(n) for each value of n from s to t.
- If the path is not valid, then return the max_value.
-
Else, we will find the minimum edge present in the path P,
flow = min(C(n)-F(n)), max_flow += flow
F(n) += flow
Step 3: Return the max_value.