一种求解网络图最大流的新算法

• 作者: 董方 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 增广链 增广链算法 度差 容差
• 年，卷（期）: 2014,（2）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 120-122,126
• 页数: 4页
• 分类号: TP301.6
• 字数: 2229字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2014.02.029

摘要

给出一种求解网络最大流的新算法，该算法是针对增广链选取的顺序不当而无法得到理想的最大流，且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念，在选择增广链时优先选择路径最短且度差较大的路径，相同层次度差相同时优先选择容差较大的路径，在饱和的弧上画上终止符。最后用实例进行了验证并和Ford-Fulkerson算法做了比较，体现了它的高效性，避免了标号，且只需要在一个图上即可完成。整个运算过程直观性强，计算方便。

作者信息

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