[1]赵礼峰 白睿 宋常城.求解网络最大流问题的标号算法[J].计算机技术与发展,2011,(12):113-115.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2011,(12):113-115.
点击复制

求解网络最大流问题的标号算法()
分享到：

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

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

文章信息/Info

Title:
Labeling Algorithm to Solve Maximum Network Flow Problem
文章编号:
1673-629X（2011）12-0113-03
作者:
赵礼峰 白睿 宋常城
南京邮电大学理学院
Author(s):
ZHAO Li-feng;  BAI Rui;  SONG Chang-cheng
School of Science, Nanjing University of Posts and Telecommunications
关键词:
最大流; Ford—Fulkerson标号算法; 增广链; 标号
Keywords:
maximum network flow; Ford-Fulkerson labeling algorithm; augmented chain; labeling
分类号:
TP301.6
文献标志码:
A
摘要:
给出了一种新的求解网络流问题的标号算法，对每个顶点进行标号，顶点有几个人弧，即有几个标号，每次在选择路径时先选取只有一个标号的路径，当所有单标号的路径走完时，再按照弧容量较大且最短的路径选择增广链。通过对Ford—Fulkerson标号算法进行改进，使得该算法容易理解，且又避免了Ford—Fulkerson标号算法在求解网络最大流问题时需经过多次的调整与标号，从而大大提高了求解最大流执行的效率。该算法通过实例给出了具体算法步骤并且表明了算法的实用性
Abstract:
It provides a new way-labeling algorithm to solve network flow. Every vertex is labeled and vertex has the same number in arc as grades. Choose the way that has a grade. After every way that has only a grade,choose the way that has bigger arc capacity and shorter path. The algorithm is easy to understand and avoids the shortcomings of several labeling and adjusting process through improving Ford- Fulkerson labeling algorithm. The algorithm improves efficiency to solve the maximum network flow. The algorithm gives specific steps and manifests the practices of the algorithm through example

相似文献/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,(12):162.
[2]赵礼峰 盂晓婉.基于深度优先的一种网络最大流求解法[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.
[3]赵礼峰,董方.一种求解网络图最大流的新算法[J].计算机技术与发展,2014,24(02):120.
　ZHAO Li-feng,DONG Fang.A New Algorithm for Solving Maximum Flow[J].,2014,24(12):120.
[4]赵礼峰,陶晓莉. 网络最大流问题的改进算法[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.
[5]赵礼峰,纪亚宝. 最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(08):52.
　ZHAO Li-feng,JI Ya-bao. Improved Shortest Augmenting Chain Algorithm of Maximum Flow[J].,2016,26(12):52.
[6]赵礼峰,纪亚劲. 基于最短增广链的最大流改进算法[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.
[7]邵丽萍,赵礼峰.最大流问题的最短增广链改进算法[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]
[8]邵丽萍,赵礼峰.基于宽度优先的网络最大流求解算法[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]
[9]罗甜甜,赵礼峰.基于重置顶点下标的网络最大流算法[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]

备注/Memo

备注/Memo:
国家自然科学基金（61070234,61071167）赵礼峰（1959-），男，安徽淮北人，教授，硕士研究生导师，研究方向为图论及其应用
更新日期/Last Update: 1900-01-01