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

在最大流问题中，由于Ford-Fulkerson算法中增广链选取的任意性，导致该算法不是有效的多项式算法。经典的最短增广链算法是通过在增广过程中寻找最短增广链，从而排除增广链选取的任意性。但计算过程中为寻找最短增广链，需要根据原网络循环地构建剩余网络和剩余分层网络，步骤非常繁杂。为改善以上不足，基于经典最短增广链算法，提出改进最短增广链算法。该算法的思想是：若在增广剩余分层网络中流值的过程中得到饱和弧，则删除该弧对应于原网络中的弧，使原网络得以简化，以此可降低构建剩余网络和剩余分层网络的复杂性，从而优化最短增广链算法。理论和仿真实验都表明，改进算法不仅正确，而且比原算法效率更高