[1]赵礼峰 陈华 宋常城 白睿.基于一个网络图最大流算法的改进[J].计算机技术与发展,2010,(12):162-165.
　ZHAO Li-feng,CHEN Hua,SONG Chang-cheng,et al.Improvement of an Algorithm Solving Maximum Flow Based on a Network Diagram[J].,2010,(12):162-165.
点击复制

基于一个网络图最大流算法的改进()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2010年12期
页码:
162-165
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Improvement of an Algorithm Solving Maximum Flow Based on a Network Diagram
文章编号:
1673-629X（2010）12-0162-04
作者:
赵礼峰 陈华 宋常城 白睿
南京邮电大学理学院
Author(s):
ZHAO Li-feng; CHEN Hua; SONG Chang-cheng; BAI Rui
College of Mathematics and Physics,Nanjing University of Posts and Telecommunications
关键词:
最大流; 增广链; Ford-Fulkerson算法; 增广链算法; 容差; 消链
Keywords:
maximum flow;  augmenting path;  Ford-Fulkerson algorithm;  augmenting path algorithm;  tolerance;  eliminating chain
分类号:
TP301.6
文献标志码:
A
摘要:
现有的求解网络最大流算法,存在由于增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题。针对上述问题展开讨论,并对一些最大流算法进行改进。利用分层网络及容差的概念,在选择增广链的时候优先选择路径最短且容差较大的路径,并将已饱和的弧画上终止符。最后通过具体的算例验证了改进算法可以简单快速地找到增广链,且避免了标号过程,只需要在一个图上即可完成。整个运算过程,直观性强,计算方便。改进的算法较其他的算法具有高效性和实用性的优势
Abstract:
Because of improper selection order of augmented path, the existing algorithm for solving the maximum networks flow,can not obtain the ideal maximum flow,and each step in the calculation of the process needs to draw a network diagram.Discuss these questions,and do some improvement of the existing algorithms.The improved algorithm makes use of layered network and the concept of tolerance,gives priority to the shortest path and greater tolerance when choosing augmenting path,and draws terminators on the arcs have reached saturation.Finally,practical examples demonstrate that the algorithm can find the augmented path easily and quickly,and avoid the labeling process,the entire operation process only needs drawing a diagram to be completed.It is strong intuitive and convenient to calculate.The improved algorithm has the advance of efficiency and practicality comparing with the existing algorithms

相似文献/References:

[1]赵礼峰,纪亚宝. 最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(08):52.
　ZHAO Li-feng,JI Ya-bao. Improved Shortest Augmenting Chain Algorithm of Maximum Flow[J].,2016,26(12):52.
[2]赵礼峰,纪亚劲. 基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(08):88.
　ZHAO Li-feng,JI Ya-jin. Improved Algorithm of Maximum Flow with Shortest Augmenting Chain[J].,2017,27(12):88.
[3]邵丽萍,赵礼峰.最大流问题的最短增广链改进算法[J].计算机技术与发展,2019,29(05):58.[doi:10. 3969 / j. issn. 1673-629X. 2019. 05. 012]
　SHAO Li-ping,ZHAO Li-feng.Shortest Augmented Chain Improvement Algorithm for Maximum Flow Problem[J].,2019,29(12):58.[doi:10. 3969 / j. issn. 1673-629X. 2019. 05. 012]
[4]邵丽萍,赵礼峰.基于宽度优先的网络最大流求解算法[J].计算机技术与发展,2019,29(06):62.[doi:10. 3969 / j. issn. 1673-629X. 2019. 06. 013]
　SHAO Li-ping,ZHAO Li-feng.An Algorithm for Solving Maximum Flow Based on Breadth First Search[J].,2019,29(12):62.[doi:10. 3969 / j. issn. 1673-629X. 2019. 06. 013]
[5]罗甜甜,赵礼峰.基于重置顶点下标的网络最大流算法[J].计算机技术与发展,2020,30(10):26.[doi:10. 3969 / j. issn. 1673-629X. 2020. 10. 005]
　LUO Tian-tian,ZHAO Li-feng.A Network Maximum Flow Algorithm Based on Reset Vertex Subscript[J].,2020,30(12):26.[doi:10. 3969 / j. issn. 1673-629X. 2020. 10. 005]
[6]赵礼峰 白睿 宋常城.求解网络最大流问题的标号算法[J].计算机技术与发展,2011,(12):113.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2011,(12):113.
[7]赵礼峰 盂晓婉.基于深度优先的一种网络最大流求解法[J].计算机技术与发展,2012,(10):161.
　ZHAO Li-feng,MENG Xiao-wan.An Algorithm for Solving Maximum Flow Based on Depth First Search[J].,2012,(12):161.
[8]赵礼峰,董方.一种求解网络图最大流的新算法[J].计算机技术与发展,2014,24(02):120.
　ZHAO Li-feng,DONG Fang.A New Algorithm for Solving Maximum Flow[J].,2014,24(12):120.
[9]赵礼峰,陶晓莉. 网络最大流问题的改进算法[J].计算机技术与发展,2014,24(11):54.
　ZHAO Li-feng,TAO Xiao-li. An Improved Algorithm for Solving Problem of Network Maximum Flow[J].,2014,24(12):54.

备注/Memo

备注/Memo:
南京邮电大学科研基金项目（NY207149）赵礼峰（1959-），男，安徽淮北人，教授，硕士研究生导师，研究方向为图论及其应用
更新日期/Last Update: 1900-01-01