求解最大流问题的算法

为提高网络最大流问题的算法效率,通过减弱对最短增广链算法的约束,给出一种增载轨算法。将剩余网络替换成余网络,它不必记录分层剩余网络邻接矩阵;根据余网络的特点,进一步将余网络划分成若干个区域,降低算法的空间复杂度。实验结果表明,在BA无标度网络中该算法与最短增广链算法的计算结果相同,其运行效率比最短增广链算法高,为大规模网络最大流问题提供了较为高效的求解算法。

Algorithm for solving maximum flow problem

To increase the algorithm efficiency of the network maximum flow problem,an augmenting path algorithm was proposed by relaxing constraints of shortest augmenting chain.The residual network was replaced with a remainder network,which eliminated the needs to record the adjacency matrix of the hierarchical residual network.At the same time,the remainder network was divided into several regions according to the characteristics of the remaining network,thereby reducing the spatial complexity of the algorithm.Results of simulation show that the calculation results of the proposed algorithm and the shortest augmented chain algorithm are the same in BA scale-free networks,and the proposed one is more efficient than the shortest augmented chain algorithm,which provides a relatively efficient solution algorithm for the maximum flow problem of large-scale network.