求解最小费用最大流的新方法

摘要：

文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性.

关键词：最小费用最大流、最大容量、单位费用、剩余网络

所属期刊栏目：22

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目61070234,61071167

在线出版日期：2012-07-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：94-96