[1]赵礼峰,董方.一种求解网络图最大流的新算法[J].计算机技术与发展,2014,24(02):120-122.
　ZHAO Li-feng,DONG Fang.A New Algorithm for Solving Maximum Flow[J].,2014,24(02):120-122.
点击复制

一种求解网络图最大流的新算法()
分享到：

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

卷:
24
期数:
2014年02期
页码:
120-122
栏目:
智能、算法、系统工程
出版日期:
2014-02-28

文章信息/Info

Title:
A New Algorithm for Solving Maximum Flow
文章编号:
1673-629X（2014）02-0120-03
作者:
赵礼峰; 董方
南京邮电大学 理学院
Author(s):
ZHAO Li-feng; DONG Fang
关键词:
最大流; 增广链; 增广链算法; 度差; 容差
Keywords:
maximum flow; augmented chain; augmented chain algorithm; degree of difference; allowance
分类号:
TP301.6
文献标志码:
A
摘要:
给出一种求解网络最大流的新算法，该算法是针对增广链选取的顺序不当而无法得到理想的最大流，且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念，在选择增广链时优先选择路径最短且度差较大的路径，相同层次度差相同时优先选择容差较大的路径，在饱和的弧上画上终止符。最后用实例进行了验证并和Ford-Fulkerson算法做了比较，体现了它的高效性，避免了标号，且只需要在一个图上即可完成。整个运算过程直观性强，计算方便。
Abstract:
It provided a new algorithm for solving maximum network flow. Due to the improper selection order of augmented chain could not obtain the ideal maximum flow and each step in the process of calculation needs to draw a network diagram,the algorithm does some improvement. The new algorithm makes use of layered network and the concept of degree of difference,gives priority to the shortest path and greater degree of difference when choosing augmenting path. It gives priority to the greater allowance path when degrees of difference are same under the same layer. And draws terminators on the arcs have reached saturation. Finally the algorithm is proved through the ex-ample and makes comparison with Ford-Fulkerson algorithm,showing its efficiency,and avoiding the labeling process,the entire process only needs drawing a diagram to be completed. It is strongly intuitive and convenient to calculate.

相似文献/References:

[1]赵礼峰,纪亚宝. 最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(08):52.
　ZHAO Li-feng,JI Ya-bao. Improved Shortest Augmenting Chain Algorithm of Maximum Flow[J].,2016,26(02):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(02):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(02):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(02):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(02):26.[doi:10. 3969 / j. issn. 1673-629X. 2020. 10. 005]
[6]赵礼峰 陈华 宋常城 白睿.基于一个网络图最大流算法的改进[J].计算机技术与发展,2010,(12):162.
　ZHAO Li-feng,CHEN Hua,SONG Chang-cheng,et al.Improvement of an Algorithm Solving Maximum Flow Based on a Network Diagram[J].,2010,(02):162.
[7]赵礼峰 白睿 宋常城.求解网络最大流问题的标号算法[J].计算机技术与发展,2011,(12):113.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2011,(02):113.
[8]赵礼峰 盂晓婉.基于深度优先的一种网络最大流求解法[J].计算机技术与发展,2012,(10):161.
　ZHAO Li-feng,MENG Xiao-wan.An Algorithm for Solving Maximum Flow Based on Depth First Search[J].,2012,(02):161.
[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(02):54.

更新日期/Last Update: 1900-01-01