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

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

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

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.