摘要
本文在求最短路和求最大流标号法的基础上,提出了求解最小费用流的复合标号法。利用这种方法可以在一次标号的过程中找到具有最小费用的增广链。该算法具有简单、易行、迭代次数少,而且易于理解的特点。
This paper presents a new mixed labelling algorithm for solving minimum cost flow problem on the basis of labelling algorithms for solving shortest path and maximum flow problems in the network. With the aid of the said method the augmentable chain with the minimum cost can be found in a single labelling process. This algorithm has the advantages of simplicity, feasibility, low computation cost and easy understanding.
关键词
图论
标号法
最小费用流
网络法
graph theory, labelling algorithm, network method, network flow programming, minimum cost flow