最小费用最大流的改进算法  

An Improved Algorithm for Min-Cost Max-Flow

作　　者：唐四云 罗操 张倩 TANG Si-yun;LUO Cao;ZHANG Qian(School of Mathematics and Systems Science, Guangdong Polytechnic Normal University;School of ComputerScience, Guangdong Polytechnic Normal University, Guangzhou Guangdong 510665)

机构地区：[1]广东技术师范大学数学与系统科学学院 [2]广东技术师范大学计算机科学学院,广东广州510665

出　　处：《广东技术师范学院学报》2019年第3期10-14,共5页Journal of Guangdong Polytechnic Normal University

基　　金：广东省自然科学基金(2018A030313546)

摘　　要：目前出现的最小费用最大流算法都有自身的缺陷,一般情况下都能达到最大流,但费用和效率达不到理想状态.鉴于算法核心是在赋权图中搜索费用最短路,本文结合最短路算法和赋权图的特点,提出了对最小费用最大流算法的改进.改进算法易理解且便于计算,通过对实例的Lingo编程实现,进一步论证改进算法的可行性.The present existing algorithm for min-cost max-flow has its defect. Usually, its flow can reach maximum, but its cost and efficiency cannot reach the ideal effect. Given the heart of the algorithm being to search the minimum cost path in weighed graph, an improved algorithm for Min-Cost Max-Flow which combines the shortest path algorithm and the character of the weighted network graph is put forward. The present algorithm is easy to understand. By implementing the instance using Lingo, the result further shows that the present algorithm is feasible.

关 键 词：最小费用最大流 最短路算法 负权值 

分 类 号：O157.5[理学—数学]