几种网络最大流算法比较

while(bfs()){

while(cur_flow=dfs(1,INF)) ans+=cur_flow; }

return ans; }

int main() {

int t,i,cas=0,u,v,w; scanf(\ while(t--){

memset(s,0,sizeof(s)); scanf(\ for(i=1;i<=m;i++){

scanf(\ if(u==v)continue; s[u][v]+=w; }

printf(\ }

return 0; }

3.4 算法比较

本文介绍了Ford-Fulkerson算法、Edmonds-Karp修正算法以及Dinic算法，这3个算法都是网络最大流算法中较为经典的算法，各自都有各自的特点，下面就将它们的特点比较一下。

Ford-Fulkerson算法的是采用深度优先策略，是网络最大流的基础算法；Edmonds-Karp算法是对顶点给标记的过程采用了宽度优先的策略，用宽度优先取代了深度优先，从而使得流量增加总是沿着长度最短的那条路径从s流向t的；Dinic算法是将顶点按照其与发点的最短距离分层，它兼取了Ford-Fulkerson算法和

5 1

Edmonds-Karp修正算法的优点，在分层时用宽度优先法，寻求增广路径时用深度优先策略。

Ford-Fulkerson算法时间复杂度为O(m*n*u)，其中m为弧的数目，n是迭代次数，u为弧上容量最大上界，是伪多项式的算法。邻接表来表示图，空间复杂度为O(m+n)；Edmonds-Karp算法由于用宽度优先，每次找到的可改进路是最短的可改进路，通过分析可以知道其时间复杂度为O(m2n)，其中m为弧的数目，n是迭代次数。邻接表表示图，空间复杂度为（m+n）；我们通过之前的分析可以知道Dinic算法时间复杂度理论的上界是O(n2*m)，其中m为弧的数目，n是迭代次数，是多项式算法。邻接表表示图，空间复杂度为（m+n）。

Ford-Fulkerson算法的实际运行效率也取决于如何确定增广路径。如果路径选取不好，可能每次增加的流就非常少，而且算法运行时间也会非常长，甚至是无法终止，所以对增广路径寻找方法的不同导致求最大流算法的不同；Edmonds-Karp算法的实际运行效率远高于Ford-Fulkerson算法；Dinic算法是这3种算法中效率最高的，因为它兼取了前两种算法的优点,在分层时用宽度优先法，寻求增广路径时用深度优先策略。

4.结论

本文研究了几种网络最大流算法，即Ford-Fulkerson算法、Edmonds-Karp修正算法以及Dinic算法。这些算法的理论基础是图论知识，并以此来讨论最大流问题。最大流问题是一类应用广泛的问题，20世纪50年代的富克逊、福特建立的网络流理论是网络应用的重要组成部分[10]。最大流问题的核心依据是Ford-Fulkerson最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有Ford-Fulkerson算法、Edmonds-Karp修正算法、Dinic算法等算法，本论文介绍了这3种算法，并实现了各个算法。

各算法的优劣各不相同，Ford-Fulkerson算法是最基础的算法，由Fulkerson和Ford提出，但是有局限性，只是采用了深度优先策略，如果路径选取不好，可能每次增加的流就非常少，而且算法运行时间也会非常长，甚至是无法终止，所以对增广路径寻找方法的不同导致求最大流算法的不同；Edmonds和Karp针对该算法增广路径选取的任意性这一缺点对它做出了修正，产生了Edmonds-Karp修正算法，它是用宽度优先取代了深度优先；而Dinic算法则兼取前两种算法的优点，在分层时用宽

6 1

度优先法，而寻求增广路径时则采用深度优先策略，它是这三种算法中效率最高的算法。

最大流问题是网络流问题的一个重要的内容，研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便,比如说电力传输问题，供销通路问题，矿井通风网络的确定，铁路货运列车的最优调度等。在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手，不过通过分析建立模型，如果可以建立成一个网络图，转化成为最大流问题，就会找到相应的解决方法。由此，最大流问题在现实生活中是非常重要的。

参考文献：

[1] 顾基发，钱颂迪，田丰，等.运筹学［M］.北京:清华大学出版社，2006:213-215 [2] 徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2005:176-183 [3] 王桂平等.图论算法理论、实现及应用［M］.北京: 北京大学出版社，2011:214-216 [4] 张宪超，陈国良，万颖瑜.网络最大流问题研究进展［J］.计算机研究与进展，2003，40（9）：1281-1292

[5] 田丰，马仲蕃. 图与网络流理论［M］.北京：科学出版社，1987:178-184

[6] 左孝凌、李为鑑、刘永才.离散数学［M］.上海:上海科学技术文献出版社，1982:271-272 [7] Bondy JA, Mutry USR.Graph Theory with Applications［J］.IEEE Graph Theory, 1976:1-264 [8] Goldberg A V,Ros S. Beyond the flow decomposition barrier［J］.Jassoc Compute Mach,1998,45(5):783-797

[9] 赵礼峰，白睿，宋常城求解网络最大流问题的标号算法［J］.计算机技术与发展，2011，21（12）：114-115

[10] 凌永发，徐宗本.一种求解网络最大流问题的算法［J］.计算机科学，2006，33（6）：39-41 [11] 谢凡荣. 运输网络中求最小费用最大流的一个算法［J］.运筹与管理，2000（4），33-38 1281-1292

[12] Minoux M.On robust maximum flow with polyhedral umcertainty set［J］.Optim Lett.2009(3):367-376

[13] Ahuja R K,Magnanti T L,Orlin J B. Network Flows:Theory,Algorithms and Applications［M］.New Jersey:Prentice Hall,2000.134-151

[14] Zhang Xianhao. Research on the maximun network flow problem［J］.Journal of Computer

7 1

Research and Development,2003,40(9):1281-1292

[15] 赵礼峰，陈华，宋常城，等.基于一个网络图最大流算法的改进［J］.计算机技术与发展，2010，20（12）：162-165

8 1