基于最短增广链的最大流改进算法

来源：计算机技术与发展杂志2017年第08期北京时间：

作者：赵礼峰;纪亚劲

摘要：网络最大流是经典的组合优化问题,它的经典算法主要有三种,分别是Ford-Fulkerson算法、最短增广链算法(Dinic算法)和预流推进算法.Ford-Fulkerson算法中由于增广链的选取任意性而有时无法得到理想的最大流.最短增广链算法在分层剩余网络中寻找最短增广链,从而避免了增广链选取的任意性.但最短增广链算法在求解最大流过程中每次增广都需要重新寻找最短增广链,利用率不高.针对这一问题,提出了一种修复最短增广链的新算法.该算法在沿最短增广链调整流量之后,删除最短增广链流量为零的弧,且寻找合适的路径修复最短增广链,从而提高了最短增广链的使用效率,减少了最短增广链的搜索次数.应用新算法进行了BA无标度网络建模仿真.实验结果表明,该算法运行效率要高于最短增广链算法.

关键词：最大流;分层剩余网络;最短增广链;BA无标度网络