网络流的预流算法

摘要

网络流算法问题是图论中经典的算法问题。多数的经典算法用寻找增广路方法，其中Ford和Fulkerson的算法和Dinic的算法都是比较经典的。而Karzanov提出来的预流的概念对于问题的理解更加的简单，产生了一些更高效的算法。我们在本文中在主要的结果和方法上引用Karzanov，Goldberg，Tarjan的证明方法和结论，在一些小的证明上和以上的证明方法稍有不同，并和经典的算法进行对比。我们对于压入重标记最大流算法这一算法进行了较为详细的讨论，在预流这一概念下，我们可以得到结论最大距离压入重标记最大流算法能够在O(n3)时间内实施。