计算机工程

作者：罗甜甜, 赵礼峰

单位：南京邮电大学 理学院, 南京 210023

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

基金：国家自然科学基金（61304169）。

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

来源：2020年第11期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第11期