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

• 作者: 罗甜甜 赵礼峰
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最大流 分层剩余网络 交叉顶点 顶点容差 BA无标度网络
• 年，卷（期）: 2020,（11）
• 所属期刊栏目: 人工智能与模式识别
• 页码范围: 48-52
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19678/j.issn.1000-3428.0056170

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰		47	251	9.0	12.0
2	罗甜甜		2	0	0.0	0.0