基于增广链修复的最大流求解算法

• 作者: 严子恒 赵礼峰
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 最大流 增广链 增广链修复 NW小世界网络 BA无标度网络
• 年，卷（期）: 2015,（5）
• 所属期刊栏目: 网络与通信
• 页码范围: 1246-1249
• 页数: 4页
• 分类号: TP301.6
• 字数: 3529字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2015.05.1246

摘要

NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法.该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率.通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络.

作者信息

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