[1]赵礼峰,陶晓莉.最小费用最大流问题的一种新算法[J].计算机技术与发展,2014,24(01):130-132.
　ZHAO Li-feng,TAO Xiao-li.A New Algorithm for Problem of Minimum Cost Maximum Flow[J].,2014,24(01):130-132.
点击复制

最小费用最大流问题的一种新算法()
分享到：

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

卷:
24
期数:
2014年01期
页码:
130-132
栏目:
智能、算法、系统工程
出版日期:
2014-01-31

文章信息/Info

Title:
A New Algorithm for Problem of Minimum Cost Maximum Flow
文章编号:
1673-629X（2014）01-0130-03
作者:
赵礼峰; 陶晓莉
南京邮电大学 理学院
Author(s):
ZHAO Li-feng; TAO Xiao-li
关键词:
最小费用最大流; 费用差; 费用和; 增广
Keywords:
minimum cost maximum flow; cost difference; cost and; augmentation
分类号:
TP301.6
文献标志码:
A
摘要:
现有的最小费用最大流算法都有自身的缺陷，增广链的选取不当会给计算带来不便，同时费用也达不到理想的效果。鉴于对最小费用最大流算法的增广链选取和最小费用的探索，文章通过对费用差的定义给出了一种求最小费用最大流的新算法。新算法的原则是优先选择费用差最小的有向路径进行增广，当费用差相同时就选择修正后的路径。通过对最小费用最大流算法的改进，新算法易理解且便于计算。通过实例说明了新算法的有效性和执行效率。
Abstract:
The existing algorithm for minimum cost maximum flow has its defect,improper selection of augmented chain will bring incon-venience in calculation,also the cost cannot reach the ideal effect. In view of the exploration of selecting the augmented chain and making the cost minimum,in this paper,a new algorithm for the minimum cost maximum flow is given by the definition of cost difference. The new algorithm principle is that the minimum cost difference of the directed path is preferred to augment,when the cost difference at the same time,the revised path was chosen. Through the improvement of the minimum cost maximum flow algorithm,the new algorithm is easy to understand and convenient to calculate. A practical example shows the validity and efficiency of the new algorithm.

相似文献/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,(01):82.
[2]赵礼峰 白睿 宋常城.求解最小费用最大流的新方法[J].计算机技术与发展,2012,(05):94.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2012,(01):94.
[3]赵礼峰,刘艳清. 定流值比例的最小双费用流算法研究[J].计算机技术与发展,2017,27(04):94.
　ZHAO Li-feng,LIU Yan-qing. Investigation on Minimum Double Cost Flow Algorithm with Constant Value Ratio[J].,2017,27(01):94.
[4]杨焕煜,邵子朋,高汉成,等.基于博弈和网络流的任务打包定价模型[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(01):14.[doi:10. 3969 / j. issn. 1673-629X. 2021. 02. 003]

更新日期/Last Update: 1900-01-01