一种基于改进堆优化Dijkstra算法的最小费用最大流算法

• 作者: 邓国强 韩颖铮
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 最小费用最大流 Dijkstra算法 堆优化
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 8-11
• 页数: 4页
• 分类号: TP301.6
• 字数: 3122字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2020.02.002

摘要

通过最短路径算法在残存网络中搜索汇点的最小费用路径是流网络中求解最小费用最大流的主要方式,而Dijk-stra算法是最高效的最短路径算法之一.本文通过证明残存网络中不存在负循环,采用改进的堆优化Dijkstra算法在残存网络中搜索最小费用路径以提升算法的效率.实验结果表明,与经典的基于最短路径快速算法的最小费用最大流算法和基于Bellman-Ford算法的最小费用最大流算法对比,本文提出的改进算法具有更高的时间效率.

作者信息

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