Open
Description
Description:
The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that finds the maximum flow in a flow network. It uses Breadth-First Search (BFS) to find the shortest augmenting path, ensuring a time complexity of O(VE²).
Why is this needed?
This algorithm is widely used in network flow problems, such as:
- Network routing
- Bipartite matching
- Circulation problems
Tasks:
- Implement the Edmonds-Karp algorithm class using BFS for augmenting path selection.
- Ensure the function accepts a directed, weighted graph with edge capacities.
- Return the maximum flow value and the corresponding flow in the network.
- Write unit tests to verify correctness.
Metadata
Metadata
Assignees
Labels
No labels