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