Abstract: 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.

Key words:  , minnimum cost maximum flow； Dijkstra algorithm； heap optimization