基于连续最短增广链的网络最大流分析
Network Maximum Flow Analysis Base on Dinic’s Algorithm
DOI: 10.12677/CSA.2018.810164, PDF,    科研立项经费支持
作者: 李 港*, 苗金宝, 胡春安：江西理工大学，信息工程学院，江西 赣州
关键词: 连续最短增广链；网络流；最大流；增广链；Dinic； Network Flow； Maximum Flow； Augmenting Chain
摘要: 本文主要是分析连续最短增广链算法计算网络最大流的问题。先综述残留网络和层次网络的基本概念，然后分析连续最短增广链算法计算网络最大流的具体过程，再通过与Ford-Fulkerson (福特-富尔克森算法)和Edmonds-Karp (埃德蒙兹-卡普算法)算法进行比较来体现出连续最短增广链算法的突出点。通过相关性的比较，结论是连续最短增广链算法运行效果明显比Ford-Fulkerson好，且优于Edmonds-Karp。
Abstract: This paper mainly analyzes the problem of calculating the maximum flow of the network by the Dinic algorithm. First we review the basic concepts of residual networks and hierarchical networks, then analyze the specific process of calculating the maximum flow of the network by the Dinic algorithm. By comparing with the Ford-Fulkerson algorithm and the Edmonds-Karp algorithm, the highlight of the Dinic algorithm is demonstrated. Through the comparison of correlations, the con-clusion is that the Dinic algorithm works better than Ford-Fulkerson and is better than Edmonds-Karp.
文章引用：李港, 苗金宝, 胡春安. 基于连续最短增广链的网络最大流分析[J]. 计算机科学与应用, 2018, 8(10): 1510-1517. https://doi.org/10.12677/CSA.2018.810164

参考文献

[1] 张宪超, 陈国良, 万颖瑜. 网络最大流问题研究进展[J]. 计算机研究与发展, 2003, 40(9): 1281-1292.
[2] Ford, L.R.J. and Fulkerson, D.R. (1954) Maximal Flow through a Network. Canadian Journal of Mathematics, 8, 399-404.
[3] Edmonds, J. and Karp, R.M. (1972) Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM, 19, 248-264. [Google Scholar] [CrossRef] 
[4] Dinitz, E.A. (1970) Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Mathematics. Doklady, 1277-1280.
[5] 谢政. 网络算法与复杂性理论[M]. 国防科技大学出版社, 2003.
[6] 徐翠霞. 基于层次网络的最大流求解方法[J]. 潍坊学院学报, 2010, 10(4): 42-45.
[7] Peleg, D. and Peleg, D. (2016) Sparse Fault-Tolerant BFS Structures. ACM.
[8] Takahashi, T. (2016) The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate. Technical Report of IeiceCst, 24, 390-394. [Google Scholar] [CrossRef] 
[9] Lammich, P. and Sefidgar, S.R. (2016) Formalizing the Edmonds-Karp Algorithm. Interactive Theorem Proving. Springer International Publishing, 219-234.