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

A Minimum Cost Maximum Flow Algorithm Based on Improved Heap Optimization Dijkstra Algorithm

作　　者：邓国强[1] 韩颖铮[1] DENG Guo-qiang;HAN Ying-zheng(Information Network Engineering and Research Center,South China University of Technology,Guangzhou 510641,China)

机构地区：[1]华南理工大学信息网络工程研究中心

出　　处：《计算机与现代化》2020年第2期8-11,共4页Computer and Modernization

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

摘　　要：通过最短路径算法在残存网络中搜索汇点的最小费用路径是流网络中求解最小费用最大流的主要方式,而Dijkstra算法是最高效的最短路径算法之一。本文通过证明残存网络中不存在负循环,采用改进的堆优化Dijkstra算法在残存网络中搜索最小费用路径以提升算法的效率。实验结果表明,与经典的基于最短路径快速算法的最小费用最大流算法和基于Bellman-Ford算法的最小费用最大流算法对比,本文提出的改进算法具有更高的时间效率。The minimum cost path for searching for sinks in the surviving network by the shortest path algorithm is the main way to solve the minimum cost maximum flow in the flow network,and the Dijkstra algorithm is one of the most efficient shortest path algorithms.In this paper,by demonstrating that there is no negative power circle in the surviving network,the improved heap optimization Dijkstra algorithm is used to search the remaining network for the minimum cost path to improve the efficiency of the algorithm.The experimental results show that compared with the classical minimum cost maximum flow algorithm based on the shortest path fast algorithm and the minimum cost maximum flow algorithm based on Bellman-Ford algorithm,the improved algorithm proposed in this paper has higher time efficiency.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]