容差修正网络最大流2F算法

Network maximal flow 2F algorithm with tolerance

网络最大流的2F算法由于对增广链的选取过于随意,造成算法不稳定,效率较低。受堵塞网络中容差概念的启发,在搜索增广链时加入了对顶点容差的判定,优先选取顶点容差为正的顶点加入增广链中,增大了每条增广链的增量,减少了增广链的数量,提高了算法的搜索效率,并用算例表明了新算法较好的可行性及执行效率。

Network maximum flow 2F algorithm, in which the selection of augmenting chain is over random, is not stable in some degree. Considering the tolerance concept in blocking network, we add tolerance determination into augmenting chain selection, so the vertexes with positive tolerance are put into the chains in advance to increase the augments of every chain but decrease the number. The example show that algorithm is feasible and can improve the searching efficiency.