Edmond-Karp in C, C++, Java and Python

[harshitakaushik-dev]

Feature = Edmond-Karp Algorithm

The Edmonds-Karp algorithm is designed to solve the maximum flow problem in a flow network. Given a directed graph with a source vertex and a sink vertex, along with capacities assigned to the edges, the algorithm aims to determine the maximum amount of flow that can be sent from the source to the sink while respecting the capacity constraints of the edges.

• The Edmonds-Karp algorithm guarantees convergence to the maximum flow in a finite number of iterations.
• It achieves this by using BFS to find the shortest augmenting path in terms of the number of edges.
• The Edmonds-Karp algorithm is an improvement over the Ford-Fulkerson algorithm, as it ensures that each augmenting path found has the minimum number of edges, leading to better performance.

Approach :

1. Initialize the flow in all edges to 0.

2. While there exists a path from the source to the sink in the residual graph (a graph that represents available capacity on each edge):

   • Use a breadth-first search (BFS) to find an augmenting path from the source to the sink. The augmenting path consists of edges with remaining capacity.
   • Determine the maximum flow that can be sent along this path by finding the minimum capacity of the edges in the path.
   • Update the flow and residual capacities of the edges in the augmenting path by subtracting the minimum capacity from the edge capacities.

3. Return the maximum flow when no augmenting path can be found from the source to the sink.

Attributes :

• Will add code in C, C++, Java and Python
• Well-commented code for the reader to understand the flow & logic of code

I would like to work on this issue. Could you please assign it to me under SSoC '23 ? Thank You :)

[Kumar-laxmi]

refer #718