[1]赵礼峰 白睿 宋常城.求解最小费用最大流的新方法[J].计算机技术与发展,2012,(05):94-96.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2012,(05):94-96.
点击复制

求解最小费用最大流的新方法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2012年05期
页码:
94-96
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Labeling Algorithm to Solve Maximum Network Flow Problem
文章编号:
1673-629X（2012）05-0094-03
作者:
赵礼峰 白睿 宋常城
南京邮电大学理学院
Author(s):
ZHAO Li-feng;  BAI Rui;  SONG Chang-cheng
School of Science, Nanjing University of Posts and Telecommunications
关键词:
最小费用最大流; 最大容量; 单位费用; 剩余网络
Keywords:
minimum Cost maximum flow ;  maximum capacity;  unit cost ; residual network
分类号:
TP301.6
文献标志码:
A
摘要:
文中给出了一种求解网络最小费用最大流的新方法，寻找由始点到终点的每条有向链，找到有向链可通过的最大容量，根据最大容量计算出此条有向链的最小费用最大流，根据最大容量和最小费用最大流可以计算出单位费用。选取单位费用最小的有向链进行最大容量的增广。文中通过对最小费用路算法进行改进，使得该算法容易理解，却又避免了最小费用路算法每次都要经过剩余网络进行增广，从而大大提高了求解最小费用最大流执行的效率。该算法通过实例给出了具体算法步骤并且表明了算法的实用性
Abstract:
It gives a new method of solving network minimum cost maximum flow. Finding the chain from the starting point to the ending point and find the maximum capacity that the chain can pass by. According to the maximum capacity, calculate the network minimum cost and unit cost through maximum capacity and minimum cost. Choose the smallest chain of unit cost to augment with the biggest capacity. By improving the shortest path algorithm, make the algorithm understand easier and avoid to augment by residual network and enhance the efficiency of solving the minimum cost and the maximum flow. It manifests the practice of algorithm through example and specific algorithm steps

相似文献/References:

[1]赵礼峰 宋常城 白睿.基于最小费用最大流问题的“排序”算法[J].计算机技术与发展,2011,(12):82.
　ZHAO Li-feng,SONG Chang-cheng,BAI Rui.Sequence Algorithm Based on Minimum Cost and Maximum Flow[J].,2011,(05):82.
[2]赵礼峰,陶晓莉.最小费用最大流问题的一种新算法[J].计算机技术与发展,2014,24(01):130.
　ZHAO Li-feng,TAO Xiao-li.A New Algorithm for Problem of Minimum Cost Maximum Flow[J].,2014,24(05):130.
[3]杨焕煜,邵子朋,高汉成,等.基于博弈和网络流的任务打包定价模型[J].计算机技术与发展,2021,31(02):14.[doi:10. 3969 / j. issn. 1673-629X. 2021. 02. 003]
　YANG Huan-yu,SHAO Zi-peng,GAO Han-cheng,et al.Task Packaging Pricing Model Based on Game and Network Flow[J].,2021,31(05):14.[doi:10. 3969 / j. issn. 1673-629X. 2021. 02. 003]

备注/Memo

备注/Memo:
国家自然科学基金项目（61070234,61071167）赵礼峰（1959-），男，安徽淮北人，教授，硕士研究生导师，研究方向为图论及其应用；白睿（1987-），女，甘肃兰州人，硕士研究生，研究方向为图论及其应用
更新日期/Last Update: 1900-01-01