Explore every max-flow algorithm supported in FlowNet — from the classic Ford-Fulkerson to the optimal Dinic's algorithm with blocking flows.
| Algorithm | Time Complexity | Space | Best For | Year |
|---|---|---|---|---|
| Dinic's | O(V²E) | O(V+E) | General dense graphs | 1970 |
| Edmonds-Karp | O(VE²) | O(V+E) | Sparse graphs | 1972 |
| Push-Relabel | O(V²√E) | O(V+E) | Unit capacity | 1988 |
| Ford-Fulkerson | O(E·f*) | O(V+E) | Small integer caps | 1956 |
| Capacity Scaling | O(E² log U) | O(V+E) | Large capacities | 1985 |
| HLPPS (Push-Relabel) | O(V²√E) | O(V+E) | Optimal practical | 1990 |
Constructs a level graph via BFS, then finds blocking flows in the level graph using DFS. Repeats until no augmenting path exists. Significantly faster than Ford-Fulkerson for dense or large networks due to the layered structure.
The foundational max-flow algorithm. Iteratively finds augmenting paths in the residual graph using DFS and pushes flow. Simple but may not terminate with irrational capacities. Use Edmonds-Karp (BFS variant) for guaranteed termination.
A BFS-based refinement of Ford-Fulkerson that always finds the shortest augmenting path (by hop count). Guarantees polynomial time complexity regardless of edge capacities. Ideal for sparse graphs with moderate node counts.
Works by maintaining a preflow and iteratively pushing excess flow from overflowing nodes. Uses height labels to guide flow. The highest-label variant (HLPPS) achieves near-optimal performance and is used in many production systems.
Improves Ford-Fulkerson by processing edges in phases based on capacity thresholds. Starts with the largest capacities and scales down, ensuring each phase augments significant flow. Effective when capacity values vary widely.
Extends max-flow with edge costs. Finds the maximum flow with minimum total cost. Uses successive shortest paths (Dijkstra/Bellman-Ford) on the residual graph. Essential for assignment problems and transportation networks.
For each edge (u→v, cap c, flow f), the residual graph contains forward edge with remaining capacity (c−f) and backward edge with capacity f. Augmenting paths are found in the residual graph.
A path from source S to sink T in the residual graph where every edge has positive residual capacity. Pushing flow along an augmenting path increases total flow.
By the max-flow min-cut theorem, the maximum flow equals the minimum cut capacity. FlowNet highlights the min-cut partition after running any max-flow algorithm.