基于宽度优先的网络最大流求解算法

• 作者: 赵礼峰 邵丽萍
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 剩余网络 增广链修复 宽度优先搜索 BA无标度网络
• 年，卷（期）: 2019,（6）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 62-65
• 页数: 4页
• 分类号: TP301.6
• 字数: 2315字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2019.06.013

摘要

网络最大流问题是经典的组合优化问题,为了降低求解大规模网络最大流的计算量,若用Ford-Fulkerson算法寻找增广链,则效率不高且步骤繁杂.为了改善以上不足,在原有算法的基础上作了一些改进,应用图的宽度优先搜索原理,针对单源单汇网络提出了一种新的求解最大流问题的算法.该算法的思想是:用宽度优先搜索原理,寻找一条包含剩余容量最大的弧的最短增广链后,删除饱和弧,且沿合适的路径修复包含剩余容量最大的弧的最短增广链.该算法避免了Ford-Fulkerson算法的标号过程,减少了反复重新寻找增广链的次数,为在大规模网络中快速获取最大流的求解提供了方便并提高了求解网络最大流的执行效率.通过实例分析与BA无标度网络建模仿真,验证了该算法的实用性,且新算法的运行效率高于Ford-Fulkerson算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	邵丽萍	南京邮电大学理学院	3	2	1.0	1.0