基于一个网络图最大流算法的改进

• 作者: 宋常城 白睿 赵礼峰 陈华
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 增广链 Ford-Fulkerson算法 增广链算法 容差 消链
• 年，卷（期）: 2010,（12）
• 页码范围: 162-165,176
• 分类号: TP301.6
• 字数: 4276字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2010.12.041

摘要

现有的求解网络最大流算法,存在由于增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题.针对上述问题展开讨论,并对一些最大流算法进行改进.利用分层网络及容差的概念,在选择增广链的时候优先选择路径最短且容差较大的路径,并将已饱和的弧画上终止符.最后通过具体的算例验证了改进算法可以简单快速地找到增广链,且避免了标号过程,只需要在一个图上即可完成.整个运算过程,直观性强,计算方便.改进的算法较其他的算法具有高效性和实用性的优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	陈华	南京邮电大学理学院	3	23	2.0	3.0
3	宋常城	南京邮电大学理学院	4	58	4.0	4.0
4	白睿	南京邮电大学理学院	4	58	4.0	4.0