Ford-Fulkerson
The general max-flow method: repeatedly find any augmenting path in the residual graph (here via DFS) and push its bottleneck capacity. Correct for any path-finding strategy, but a poor choice of paths can make it slow on adversarial graphs.
- Category
- Graphs
- Time complexity
- O(E · maxFlow)
- Space complexity
- O(V + E)
Pseudocode
while a residual S→T path exists find one (any strategy) bottleneck = min residual capacity on it push bottleneck flow along it
Reference implementation
flow = 0
while path := find_path(residual_graph, S, T):
b = min(residual capacities on path)
for edge in path: update_flow(edge, b)
flow += b