Open AdiChat opened 7 years ago
I would like to contribute to this.
I am working on the C++ code
I'll do it in Python
Added the Python implementation for ford fulkerson in #294
Shouldn't the ones currently in here using BFS for finding augmenting paths be moved to Edmonds-Karp instead? As Ford-Fulkerson doesn't actually specify what algorithm should be used for finding them.
It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified [...]
The algorithm is identical to the Ford–Fulkerson algorithm, except that the search order when finding the augmenting path is defined. The path found must be a shortest path that has available capacity. This can be found by a breadth-first search, where we apply a weight of 1 to each edge.
Also noticed that at least the python algorithm for Ford-Fulkerson using BFS doesn't take edge weights into account, so it will find shortest paths, and thus be Edmonds-Karp.
Could perhaps leave Ford-Fulkerson in, but make it take an argument that is the function for finding augmenting paths. Then you could make Edmonds-Karp simply be a call to Ford-Fulkerson with BFS as the augmenting path-finding algorithm.
Add the code for
Ford fulkerson algorithm for maximum flow
in any language (C
,C++
,Java
,Go
,Python
or any other)The code should be placed at code/graph-algorithms/ford_fulkerson_maximum_flow/
Note: multiple contributors can work on this issue as it has multiple parts (languages)
Your pull request will be reviewed by maintainers instantly.
For contribution guidelines, see this
If you need any help, let us know.