在最大流问题中，由于Ford-Fulkerson算法中增广链选取的任意性，导致该算法不是有效的多项式算法。经典的最短增广链算法是通过在增广过程中寻找最短增广链，从而排除增广链选取的任意性。但计算过程中为寻找最短增广链，需要根据原网络循环地构建剩余网络和剩余分层网络，步骤非常繁杂。为改善以上不足，基于经典最短增广链算法，提出改进最短增广链算法。该算法的思想是：若在增广剩余分层网络中流值的过程中得到饱和弧，则删除该弧对应于原网络中的弧，使原网络得以简化，以此可降低构建剩余网络和剩余分层网络的复杂性，从而优化最短增广链算法。理论和仿真实验都表明，改进算法不仅正确，而且比原算法效率更高。%In maximum flow problem,since the Ford-Fulkerson algorithm chooses arbitrarily augmented chain,as a result the algorithm is not a valid polynomial one. Classical shortest augmenting chain algorithm is to find the shortest augmenting chain in the augmented chain process,thus eliminating the arbitrary of augmented chain selection. But in calculation process for finding the shortest augmenting chain, needing to build the remaining network and the remaining surplus hierarchical network based on the original network cycle,its step is very complicated. In order to improve the above problems,based on the classical shortest augmenting chain algorithm,an improved one for the shortest augmenting chain is put forward. The idea is that if the saturated arc is obtained in flow value processing augmented remaining hi-erarchical network,then the original arc corresponding to the network is deleted,making the original network simplified in order to reduce the complexity of constructing remaining network and the remaining layered network and optimize the shortest augmenting chain algo-rithm. The theory and simulation show that the improved algorithm is not only correct,but also higher in efficiency than the original algo-rithm.
展开▼
