# Maximum flow running time depend on longest path

Consider a directed graph with specified vertices $s$ and $t$. The graph has $m$ edges and $n$ vertices with length of the longest simple $st$-path to be $k$. Dinic's algorithm finds a maximum flow consists of blocking flow computations, where each takes $O(m\log n)$ time with dynamic trees [1,2]. After each blocking flow, the distance between $s$ and $t$ in the residual graph increases by at least $1$. Therefore there are at most $k$ blocking flow computations. Dinic's algorithm takes $O(km\log n)$ time to find a maximum $st$-flow.

# References

[1] D.D. Sleator, R.E. Tarjan, **A Data Structure for Dynamic Trees**, J. Comput. Syst. Sci. 26 (1983) 362–391 10.1016/0022-0000(83)90006-5.

[2] Y. Dinitz, Theoretical computer science, in: O. Goldreich, A.L. Rosenberg, A.L. Selman (Eds.), Springer-Verlag, Berlin, Heidelberg, 2006: pp. 218–240.