摘要
网络最大流的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.
出处
《长春工业大学学报》
CAS
2008年第6期713-716,共4页
Journal of Changchun University of Technology
关键词
网络最大流
2F算法
增广链
容差
network maximal flow
2F algorithm
augmenting chain
tolerance