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

Shortest Augmented Chain Improvement Algorithm for Maximum Flow Problem

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

BA (Barabasi-Albert) scale-free network is a common network in reality.In this network,there exists multiple paths between any two nodes in high possibility.If the Ford-Fulkerson algorithm is used to find the augmented chain,the efficiency is not high and the steps are complicated.At the same time,in the context of the big data,with the increase of network scale,improving algorithm efficiency becomes the key to solve the problem of maximum flow in large-scale networks.In order to improve the above shortcomings,based on the shortest augmented chain algorithm,we make some improvements and propose an improved shortest augmented chain algorithm.The arcs that have no effect in the original network are deleted;the saturated arcs that are deleted in the original network are correspondingly deleted from the layered residual network,which reduces the complexity of constructing the residual remaining network and the layered residual network and optimizes the shortest augmented chain algorithm.The experiment shows that the results of the new algorithm is the same as that of the shortest augmented chain algorithm in BA scale-free network,and the operation efficiency is higher than that of the shortest augmented chain algorithm.