网络最大流问题的改进算法

• 作者: 赵礼峰 陶晓莉
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 容量差 增广链 最短路径
• 年，卷（期）: 2014,（11）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 54-56
• 页数: 3页
• 分类号: TP301.6
• 字数: 1619字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2014.11.014

摘要

网络最大流问题是图论中的经典问题之一，对于最大流问题有很多经典的算法，但这些经典算法皆有不足之处。针对其不足，文中通过引入容量差的概念，对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广，若当路径长度一样并且容量差也一样时就要对其修正，然后选择修正后的路径，这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性，整个运算过程可以在一个图上完成，直观性强并且方便计算，较传统算法更为有效。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	陶晓莉	南京邮电大学理学院	2	13	1.0	2.0