基于层弧容量比求解网络最大流

• 作者: 朱雨 赵礼峰
• 来源期刊: 电视技术
• 学科: 工学
• 关键词: 最大流 分层 增广路径 关键弧 BA无标度网络
• 年，卷（期）: 2020,（6）
• 所属期刊栏目: 网络与融合
• 页码范围: 1-5
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.16280/j.videoe.2020.06.001

摘要

针对最短增广链算法一开始选取增广路径的随意性,给出了一种在单源、单汇网络中通过层弧容量比来求解网络最大流的新算法.该改进算法的思想是运用宽度优先搜索的方法,在改进的分层剩余网络中找到与汇点相邻接且容量最大的弧(称为关键弧),再选择含有关键弧的最短增广路径,根据制定的规则,从而有序地进行流值增广,直至没有可增广的路径终止.在BA无标度网络中进行实验,发现新算法的效率略高于最短增广链算法,且能把关键弧的容量更加合理地分配给上一层弧,提高了最大流的流值.

作者信息

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