Find the maximum flow using Ford Fulkerson Method Edmond Karp’s Algorithm.

Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source and sink in the graph. Find the maximum possible flow from source to sink.

Algorithm:

1. Create residualGraph from capacityGraph just by coping value from there to here
2. Set maxFlow = 0
3. Iterate till augmenting path exists in residualGraph (for augmenting path use BFS for DFS)
   1. Compute bottleneck capacity of augmenting path
   2. Decrease bottleneck capacity from each edge of augmenting path
   3. Increase bottleneck capacity from each reverse edge of augmenting path
   4. Add bottleneck capacity to maxFlow

Video

Video

Why add bottleneck capacity to reverse edge

Latest Source Code:
Github: MaximumFlow.java

Output:

 Paths are: 
[0, 1, 2, 4, 6]
[0, 3, 5, 6]
[0, 1, 2, 3, 5, 6]
Max flow: 5