[1]邵丽萍,赵礼峰.最大流问题的最短增广链改进算法[J].计算机技术与发展,2019,29(05):58-61.[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(05):58-61.[doi:10. 3969 / j. issn. 1673-629X. 2019. 05. 012]
点击复制

最大流问题的最短增广链改进算法()
分享到：

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

卷:
29
期数:
2019年05期
页码:
58-61
栏目:
智能、算法、系统工程
出版日期:
2019-05-10

文章信息/Info

Title:
Shortest Augmented Chain Improvement Algorithm for Maximum Flow Problem
文章编号:
1673-629X(2019)05-0058-04
作者:
邵丽萍; 赵礼峰
南京邮电大学 理学院,江苏 南京 210023
Author(s):
SHAO Li-ping; ZHAO Li-feng
School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
关键词:
最大流; 最短增广链; 剩余网络; 分层剩余网络; BA无标度网络
Keywords:
maximum flow; shortest augmented chain; residual network; layered residual network; BA scale-free network
分类号:
TP301. 6
DOI:
10. 3969 / j. issn. 1673-629X. 2019. 05. 012
摘要:
BA 无标度网络是现实中常见的网络,在该网络中,任意两节点之间有极大可能存在多条路径,若用 Ford - Fulkerson 算法寻找增广链,效率不高且步骤繁杂。 同时,在当今大数据时代背景下,随着网络规模的增加,提高算法效率成为解决大规模网络最大流问题的关键。 为了改善以上不足,文中在最短增广链算法的基础上作了一些改进,提出了最短增广链改进算法。 该算法基于最短增广链算法,删除原网络中没有起作用的弧;在分层剩余网络中删除的饱和弧,相应的在原网络中删除该弧,降低构建剩余网络和分层剩余网络的复杂性,从而优化最短增广链算法。 实验结果表明,在 BA无标度网络中该算法与最短增广链算法的计算结果相同,并且运行效率比最短增广链算法有所提高。
Abstract:
BA (Barabasi-Albert) scale-free network is a common network in reality. In this network,there exists multiple paths between any two nodes in high possibility. If the Ford-Fulkerson algorithm is used to find the augmented chain,the efficiency is not high and the steps are complicated. At the same time,in the context of the big data,with the increase of network scale,improving algorithm efficiency becomes the key to solve the problem of maximum flow in large-scale networks. In order to improve the above shortcomings,based on the shortest augmented chain algorithm,we make some improvements and propose an improved shortest augmented chain algorithm. The arcs that have no effect in the original network are deleted;the saturated arcs that are deleted in the original network are correspondingly deleted from the layered residual network,which reduces the complexity of constructing the residual remaining network and the layered residual network and optimizes the shortest augmented chain algorithm. The experiment shows that the results of the new algorithm is the same as that of the shortest augmented chain algorithm in BA scale-free network,and the operation efficiency is higher than that of the shortest augmented chain algorithm.

相似文献/References:

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

更新日期/Last Update: 2019-05-10