基于有效反向网络的最大流算法

• 作者: 邓国强 陆以勤 韩颖铮
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 最大流 流网络 有效反向网络 最短增广链
• 年，卷（期）: 2018,（z1）
• 所属期刊栏目: 网络新技术及其应用
• 页码范围: 179-183
• 页数: 5页
• 分类号: TP301.6
• 字数: 3501字
• 语种: 中文
• DOI: 10.11959/j.issn.1000-436x.2018189

摘要

针对经典的最大流Dinic算法反复沿着无效路径搜索造成的时间浪费问题,提出了一种基于有效反向网络的最大流算法.算法修改了汇点的深度定义,在计算节点深度过程中构建了有效反向网络,从汇点出发搜索增广路径,降低了节点深度计算的次数,同时避免了反复搜索无效路径.实验结果表明,基于有效反向网络的最大流算法的求解速度优于Dinic算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陆以勤	华南理工大学信息网络工程研究中心	56	292	8.0	15.0
2	韩颖铮	华南理工大学信息网络工程研究中心	16	16	3.0	3.0
3	邓国强	华南理工大学信息网络工程研究中心	11	9	2.0	2.0