# 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 http://dx.doi.org/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.

Posted by Chao Xu on 2016-07-02.
Tags: flow.