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

摘要：

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

关键词：最大流、增广链、增广链修复、NW小世界网络、BA无标度网络

所属期刊栏目：35

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2015-07-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1246-1249