[1]罗甜甜,赵礼峰.基于重置顶点下标的网络最大流算法[J].计算机技术与发展,2020,30(10):26-30.[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(10):26-30.[doi:10. 3969 / j. issn. 1673-629X. 2020. 10. 005]
点击复制

基于重置顶点下标的网络最大流算法()
分享到：

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

卷:
30
期数:
2020年10期
页码:
26-30
栏目:
智能、算法、系统工程
出版日期:
2020-10-10

文章信息/Info

Title:
A Network Maximum Flow Algorithm Based on Reset Vertex Subscript
文章编号:
1673-629X(2020)10-0026-05
作者:
罗甜甜; 赵礼峰
南京邮电大学 理学院,江苏 南京 210023
Author(s):
LUO Tian-tian; ZHAO Li-feng
School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
关键词:
最大流; 顶点层数; 源弧容量; 汇弧容量; 顶点容差
Keywords:
maximum flow; vertex layer number; source arc capacity; arcing capacity; vertex tolerance
分类号:
TP301. 6
DOI:
10. 3969 / j. issn. 1673-629X. 2020. 10. 005
摘要:
通过分析最短增广链算法中好的一面是对顶点分层的理念,不足之处在于需要反复构建分层剩余网络造成算法步骤的繁琐, 并且在构建了比原网络更轻易发现增广链的分层剩余网络后,在选取增广链时还是存在随机性,这就导致了某些增广链的丢失,使得最终流值偏小的结果。 针对这一现象,提出了一种重置顶点下标的最大流改进算法。该算法首先根据每个顶点在整个网络图中所处位置的重要程度制定相应规则,然后对顶点下标按照此规则重新编号,使得网络图更加清晰直观,从而避免了最短增广链算法中反复构造分层剩余网络图的缺陷。 而且新算法还增加了寻找增广链的方法用以规避随机性的缺陷,这也为后面寻找增广链有规可循节约了时间。 最后通过数值实例仿真实验证明了新算法的简易性和准确性。
Abstract:
By analyzing the positive side of the shortest augmented chain algorithm,the concept of layering the vertices is inadequate because it requires the repeated construction of a layered residual network to cause tedious algorithm steps,and it is easier to find the augmented chain than the original network. After layering the residual network, there is still randomness when selecting the augmented chain,which leads to the loss of some augmented chains,resulting in a small final flow value. Aiming at this phenomenon,an improved maximum flow algorithm for resetting the vertex index is proposed. The algorithm first formulates corresponding rules according to the importance of the position of each vertex in the entire network graph,and then renumbers the vertex subscripts in accordance with this rule,making the network graph more clear and intuitive, thereby avoiding the defects of repetitive construction of hierarchical residual network graphs in the shortest augmentation chain algorithm. In addition, the proposed algorithm also adds a method to find the augmented chain to avoid the shortcomings of randomness,which also saves time for the future to find the regularized and augmented chain. Finally,numerical examples are used to demonstrate the simplicity and accuracy of the proposed 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,(10):162.
[2]赵礼峰 白睿 宋常城.求解网络最大流问题的标号算法[J].计算机技术与发展,2011,(12):113.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2011,(10):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,(10):161.
[4]赵礼峰,董方.一种求解网络图最大流的新算法[J].计算机技术与发展,2014,24(02):120.
　ZHAO Li-feng,DONG Fang.A New Algorithm for Solving Maximum Flow[J].,2014,24(10):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(10):54.
[6]赵礼峰,纪亚宝. 最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(08):52.
　ZHAO Li-feng,JI Ya-bao. Improved Shortest Augmenting Chain Algorithm of Maximum Flow[J].,2016,26(10):52.
[7]赵礼峰,纪亚劲. 基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(08):88.
　ZHAO Li-feng,JI Ya-jin. Improved Algorithm of Maximum Flow with Shortest Augmenting Chain[J].,2017,27(10):88.
[8]邵丽萍,赵礼峰.最大流问题的最短增广链改进算法[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(10):58.[doi:10. 3969 / j. issn. 1673-629X. 2019. 05. 012]
[9]邵丽萍,赵礼峰.基于宽度优先的网络最大流求解算法[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(10):62.[doi:10. 3969 / j. issn. 1673-629X. 2019. 06. 013]

更新日期/Last Update: 2020-10-10