最大流问题的改进最短增广链算法

• 作者: 纪亚宝 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 最短增广链 剩余网络 剩余分层网络
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 52-54,59
• 页数: 4页
• 分类号: TP301.6
• 字数: 2826字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2016.08.011

摘要

在最大流问题中，由于Ford-Fulkerson算法中增广链选取的任意性，导致该算法不是有效的多项式算法。经典的最短增广链算法是通过在增广过程中寻找最短增广链，从而排除增广链选取的任意性。但计算过程中为寻找最短增广链，需要根据原网络循环地构建剩余网络和剩余分层网络，步骤非常繁杂。为改善以上不足，基于经典最短增广链算法，提出改进最短增广链算法。该算法的思想是：若在增广剩余分层网络中流值的过程中得到饱和弧，则删除该弧对应于原网络中的弧，使原网络得以简化，以此可降低构建剩余网络和剩余分层网络的复杂性，从而优化最短增广链算法。理论和仿真实验都表明，改进算法不仅正确，而且比原算法效率更高。

作者信息

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