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

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

作者：邵丽萍;赵礼峰

摘要：BA 无标度网络是现实中常见的网络,在该网络中,任意两节点之间有极大可能存在多条路径,若用 Ford - Fulkerson 算法寻找增广链,效率不高且步骤繁杂。 同时,在当今大数据时代背景下,随着网络规模的增加,提高算法效率成为解决大规模网络最大流问题的关键。 为了改善以上不足,文中在最短增广链算法的基础上作了一些改进,提出了最短增广链改进算法。 该算法基于最短增广链算法,删除原网络中没有起作用的弧;在分层剩余网络中删除的饱和弧,相应的在原网络中删除该弧,降低构建剩余网络和分层剩余网络的复杂性,从而优化最短增广链算法。 实验结果表明,在 BA无标度网络中该算法与最短增广链算法的计算结果相同,并且运行效率比最短增广链算法有所提高。

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