Implementation in C++20 of the Edmonds-Karp's algorithm and the Dinitz's algorithm (following the Boris V. Cherkassky's recommentations) for computing the maximum flow of a given flow network in O(nm²) and O(n²m) respectively. This implementation was made for educational purposes.
- Implementation of a performant push-relabel algorithm.
- A small function to compute the minimum cut with the final residual network.
This project use CMake. To run the executable you need to pass a flow network instance .max file:
$ maxflow ../maxflow_instances/BVZ-tsukuba0.max
Network instance: "../maxflow_instances/BVZ-tsukuba0.max - |V| = 110594, |E| = 514483
Algorithm: "Dinitz-Cherkassky"
Maximum flow value: 34669
Duration: 532ms
Algorithm: "Edmonds-Karp"
Maximum flow value: 34669
Duration: 15312ms
- Dinitz Y. (2006) Dinitz’ Algorithm: The Original Version and Even’s Version. In: Goldreich O., Rosenberg A.L., Selman A.L. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 3895. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11685654_10