求解网络最大流问题的标号算法

• 作者: 宋常城 白睿 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 Ford-Fulkerson标号算法 增广链 标号
• 年，卷（期）: 2011,（12）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 113-115
• 分类号: TP301.6
• 字数: 2251字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2011.12.030

摘要

给出了一种新的求解网络流问题的标号算法,对每个顶点进行标号,顶点有几个人弧,即有几个标号,每次在选择路径时先选取只有一个标号的路径,当所有单标号的路径走完时,再按照弧容量较大且最短的路径选择增广链.通过对Ford-Fulkerson标号算法进行改进,使得该算法容易理解,且又避免了Ford-Fulkerson标号算法在求解网络最大流问题时需经过多次的调整与标号,从而大大提高了求解最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性.

作者信息

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