[1]赵礼峰,陶晓莉. 网络最大流问题的改进算法[J].计算机技术与发展,2014,24(11):54-56.
　ZHAO Li-feng,TAO Xiao-li. An Improved Algorithm for Solving Problem of Network Maximum Flow[J].,2014,24(11):54-56.
点击复制

 网络最大流问题的改进算法()
分享到：

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

卷:
24
期数:
2014年11期
页码:
54-56
栏目:
智能、算法、系统工程
出版日期:
2014-11-10

文章信息/Info

Title:
 An Improved Algorithm for Solving Problem of Network Maximum Flow
文章编号:
1673-629X（2014）11-0054-03
作者:
 赵礼峰; 陶晓莉
 南京邮电大学 理学院
Author(s):
 ZHAO Li-feng; TAO Xiao-li
关键词:
 ; 最大流; 容量差; 增广链; 最短路径
Keywords:
 ; maximum flow; differential capacity; augmenting path; shortest path
分类号:
TP301.6
文献标志码:
A
摘要:
 网络最大流问题是图论中的经典问题之一，对于最大流问题有很多经典的算法，但这些经典算法皆有不足之处。针对其不足，文中通过引入容量差的概念，对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广，若当路径长度一样并且容量差也一样时就要对其修正，然后选择修正后的路径，这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性，整个运算过程可以在一个图上完成，直观性强并且方便计算，较传统算法更为有效。
Abstract:
 The maximum network flow problem is one of the classical problems in graph theory,there are many classical algorithms for them,but all theories have shortcomings. For the shortcomings,the algorithm is improved by introducing the concept of differential capac-ity. The principle of improved algorithm is that the shortest path and maximum differential capacity is priority selection. When the length of path and differential capacity are the same,can choose the revised path,so that each augmentation can make an arc reach saturation at least. An practical example is given to demonstrate the feasibility,all of the procedure can be completed in one diagram,the intuition is strong and easy to calculate,the new algorithm is more effective than the traditional 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,(11):162.
[2]赵礼峰 白睿 宋常城.求解网络最大流问题的标号算法[J].计算机技术与发展,2011,(12):113.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2011,(11):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,(11):161.
[4]赵礼峰,董方.一种求解网络图最大流的新算法[J].计算机技术与发展,2014,24(02):120.
　ZHAO Li-feng,DONG Fang.A New Algorithm for Solving Maximum Flow[J].,2014,24(11):120.
[5]张志宏,吴庆波,邵立松,等.基于飞腾平台TOE协议栈的设计与实现[J].计算机技术与发展,2014,24(07):1.
　ZHANG Zhi-hong,WU Qing-bo,SHAO Li-song,et al. Design and Implementation of TCP/IP Offload Engine Protocol Stack Based on FT Platform[J].,2014,24(11):1.
[6]梁文快,李毅. 改进的基因表达算法对航班优化排序问题研究[J].计算机技术与发展,2014,24(07):5.
　LIANG Wen-kuai,LI Yi. Research on Optimization of Flight Scheduling Problem Based on Improved Gene Expression Algorithm[J].,2014,24(11):5.
[7]黄静,王枫,谢志新,等. EAST文档管理系统的设计与实现[J].计算机技术与发展,2014,24(07):13.
　HUANG Jing,WANG Feng,XIE Zhi-xin,et al. Design and Implementation of EAST Document Management System[J].,2014,24(11):13.
[8]侯善江[],张代远[][][]. 基于样条权函数神经网络P2P流量识别方法[J].计算机技术与发展,2014,24(07):21.
　HOU Shan-jiang[],ZHANG Dai-yuan[][][]. P2P Traffic Identification Based on Spline Weight Function Neural Network[J].,2014,24(11):21.
[9]李璨,耿国华,李康,等. 一种基于三维模型的文物碎片线图生成方法[J].计算机技术与发展,2014,24(07):25.
　LI Can,GENG Guo-hua,LI Kang,et al. A Method of Obtaining Cultural Debris’ s Line Chart Based on Three-dimensional Model[J].,2014,24(11):25.
[10]翁鹤,皮德常. 混沌RBF神经网络异常检测算法[J].计算机技术与发展,2014,24(07):29.
　WENG He,PI De-chang. Chaotic RBF Neural Network Anomaly Detection Algorithm[J].,2014,24(11):29.
[11]赵礼峰,纪亚宝. 最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(08):52.
　ZHAO Li-feng,JI Ya-bao. Improved Shortest Augmenting Chain Algorithm of Maximum Flow[J].,2016,26(11):52.
[12]赵礼峰,纪亚劲. 基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(08):88.
　ZHAO Li-feng,JI Ya-jin. Improved Algorithm of Maximum Flow with Shortest Augmenting Chain[J].,2017,27(11):88.

更新日期/Last Update: 2015-04-07