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

Improved Algorithm of Maximum Flow with Shortest Augmenting Chain

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

The maximum network flow is a classic combinatorial optimization problem, which mainly consists of Ford-Fulkerson algo- rithm,the shortest augmenting chain aigorithm （Dinic algorithm） and preflow push algorithm. The desired maximum flow from Ford- Fulkerson algorithm could not he acquired because of the arbitrariness when choosing the augmented chain. The shortest augmenting chain algorithm can find the shortest augmenting chain in the remaining layered network to avoid the augmented chain selected arbitrary ,howev- er,it needs to search again shortest augmenting chain in maximum flow when augmenting with low using rate. Aimed at this problem, a new shortest augmenting chain repair algorithm is presented. After it has adjusted flow along the shortest augmenting chain the arc of zero flow on the augmented chain has been removed to retain the arc that the flow zero, which select the appropriate nodes to repair shortest augmenting chain in the remaining nodes for improving the efficiency and reducing the times of search shortest augmenting chain. The im- proved algorithm is verified through the modeling and simulation experimental in BA scale-free network, which shows that its efficiency is higher than the shortest augmenting chain algorithm.