包含交叉顶点的最大流改进算法

摘要：

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

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

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61304169

在线出版日期：2021-01-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：48-52