Maximum flow algorithms are known to perform significantly better in practice than their worst-case time complexities would suggest. So in this blog, I will present graphs on which the following maximum flow algorithms actually achieve their worst-case running time:
| Algorithm | Time Complexity |
|---|---|
| Ford-Fulkerson with DFS | $$$\mathcal{O}\big(m^2 \cdot U)$$$ |
| Edmonds-Karp | $$$\mathcal{O}\big(n \cdot m^2\big)$$$ |
| Dinic | $$$\mathcal{O}\big(n^2 \cdot m\big)$$$ |
| DFS with Scaling | $$$\mathcal{O}\big(m^2 \cdot \log(U)\big)$$$ |
| Dinic with Scaling | $$$\mathcal{O}\big(n \cdot m \cdot \log(U)\big)$$$ |
| Most Improving Augmenting Paths | $$$\mathcal{O}\big(m \cdot \log(U) \cdot (m + n \cdot \log(n))\big)$$$ |
| FIFO Preflow Push | $$$\mathcal{O}\big(n^3\big)$$$ |
| Highest-Label Preflow Push | $$$\mathcal{O}\big(n^2 \cdot \sqrt{m}\big)$$$ |
Here and in the rest of this blog:
- $$$n =$$$ number of vertices,
- $$$m =$$$ number of edges,
- $$$U =$$$ maximum edge capacity.
