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

摘要：

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

关键词：最小费用最大流、Dijkstra算法、堆优化

分类号：TP301.6(计算技术、计算机技术)

资助基金：广东省重点领域研发计划项目;赛尔网络下一代互联网技术创新项目

在线出版日期：2020-04-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：8-11