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

作者：邓国强; 韩颖铮

来源：计算机与现代化, 2020, (02): 8-11.

DOI：10.3969/j.issn.1006-2475.2020.02.002

• 最小费用最大流
• Dijkstra算法
• 堆优化

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

• 单位
  华南理工大学