摘要： 最短增广链算法构建分层剩余网络后，在面临多条相同弧数增广链且其中顶点有重合的情况下，会因寻找增广链时未考虑增广顺序而导致流值丢失。针对该问题，提出一种网络图中包含交叉顶点的最大流改进算法。该算法保留最短增广链算法的分层理念，仍在分层剩余网络中寻找增广链，在此基础上增加寻找增广链的规则，即优先搜索与源点关联且容差最小的顶点作为下一步推进点，确定一条增广链后即考虑与上一条有重合的顶点所在的增广链进行增广。实例分析与BA无标度网络建模仿真结果表明，与最短增广链算法相比，该算法得到的最大流值更准确，并且效率相当。

关键词: 最大流, 分层剩余网络, 交叉顶点, 顶点容差, BA无标度网络

Abstract: A hierarchical residual network constructed by the shortest augmented chain algorithm may lead to the loss of flow values when it faces multiple augmented chains with the same number of directed graphs and overlapped vertices,for it does not consider the augmented sequence when looking for augmented chains.In order to solve the problem,this paper proposes an improved network maximum flow algorithm with intersecting vertices in the network graph.It retains the hierarchical concept of the shortest augmented chain algorithm,and looks for augmented chains in the hierarchical residual network.On this basis,a rule is added to prioritize the search of the vertices that are related to the source vertex and with the minimum tolerance,and the vertices are taken as the new source vertices for further search.After an augmented chain is determined,the augmented chains with overlapped vertices are considered for further augmentation with the previous augmented chain.Results of example analysis and BA scale-free network modeling simulation show that,compared with the shortest augmented chain algorithm,the proposed algorithm can obtain more accurate maximum flow values while keeping same efficiency.

Key words: maximum flow, hierarchical residual network, intersecting vertice, vertice tolerance, BA scale-free network

中图分类号: 

• TP301.6