[1]纪亚劲,刘艳清,赵礼峰.求解最小费用流的一种新算法[J].计算机技术与发展,2018,28(01):108-111.[doi:10. 3969/ j. issn. 1673-629X.2018.01.023]
　JI Ya-jin,LIU Yan-qing,ZHAO Li-feng.A New Algorithm for Solving Minimum Cost Flow[J].Computer Technology and Development,2018,28(01):108-111.[doi:10. 3969/ j. issn. 1673-629X.2018.01.023]
点击复制

求解最小费用流的一种新算法()
分享到：

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

卷:
28
期数:
2018年01期
页码:
108-111
栏目:
智能、算法、系统工程
出版日期:
2018-01-10

文章信息/Info

Title:
A New Algorithm for Solving Minimum Cost Flow
文章编号:
1673-629X(2018)01-0108-04
作者:
纪亚劲; 刘艳清; 赵礼峰
南京邮电大学 理学院,江苏 南京 210023
Author(s):
JI Ya-jin; LIU Yan-qing; ZHAO Li-feng
School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
关键词:
最小费用流; Dijkstra 算法; 余网络; ER 随机网络
Keywords:
minimum cost flow; Dijkstra algorithm; remainder network; ER stochastic network
分类号:
TP301.6
DOI:
10. 3969/ j. issn. 1673-629X.2018.01.023
文献标志码:
A
摘要:
网络最小费用流问题是经典的双目标优化问题,其中利用的图论方法主要有负费用回路算法和最小费用路算法。 最小费用路(Busacker-Gowan)算法每次增广流值之前都需要搜索一次最小费用路径,导致算法复杂度偏高,并且该算法是在剩余网络的基础上进行增广,使得该算法在计算预定流值最小费用流时有点冗余。 针对这些不足,提出了一种求最小费用流的新算法。 该算法首先利用改进的 Dijkstra 算法一次搜索出所有的源点至汇点费用路径,并且在余网络中增广流值。 由于余网络比剩余网络构造简单,所以最终提高了算法的时间效率。 仿真实验表明,在 ER 随机网络中提出算法和经典算法的计算结果相同,并且提出算法不管是在稀疏网络还是非稀疏网络中其运行时间比经典算法都要少,同时更适用于稀疏网络。
Abstract:
The network minimum cost flow is a classical two-objective optimization problem,in which the graph theory mainly has the negative cost loop algorithm and the least cost path algorithm. The minimum cost path (Busacker-Gowan) algorithm needs to search once before each increment of the flow value,resulting in high complexity and it is augmented on the basis of the residual network which makes some redundancy when calculating the minimum cost flow of the predetermined flow value. Aiming at these problems,a new algorithm is proposed to solve the minimum cost flow. First it searches out all the source-sink cost paths by improved Dijkstra algorithm,and augments the flow values in the remainder network which is simpler than residual network so that the time efficiency of the algorithm is improved. In the simulation,the proposed algorithm is identical with the classical algorithm on computing results in the ER stochastic net-
work,and it has less runtime than the latter in both sparse and non-sparse networks,more suitable for sparse networks.

相似文献/References:

[1]卫泓宇,刘冠灵,谢爱倍,等.基于单目视觉的智能物料分拣机器人的设计[J].计算机技术与发展,2020,30(02):98.[doi:10. 3969 / j. issn. 1673-629X. 2020. 02. 020]
　WEI Hong-yu,LIU Guan-ling,XIE Ai-bei,et al.Design of Intelligent Material Sorting Robot Based on Monocular Vision[J].Computer Technology and Development,2020,30(01):98.[doi:10. 3969 / j. issn. 1673-629X. 2020. 02. 020]
[2]王树梅,黄 石,臧禹顺.基于 Dijkstra 算法的城市物流公交系统优化[J].计算机技术与发展,2021,31(10):179.[doi:10. 3969 / j. issn. 1673-629X. 2021. 10. 030]
　WANG Shu-mei,HUANG Shi,ZANG Yu-shun.Public Transportation System Optimization of Urban Logistics Based on Dijkstra Algorithm[J].Computer Technology and Development,2021,31(01):179.[doi:10. 3969 / j. issn. 1673-629X. 2021. 10. 030]
[3]袁玉莹,付 雄.基于扩展 Dijkstra 的多约束 QoS 路由研究[J].计算机技术与发展,2021,31(11):122.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 020]
　YUAN Yu-ying,FU Xiong.Research on Multi-constrained QoS Routing Based on Extended Dijkstra[J].Computer Technology and Development,2021,31(01):122.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 020]

更新日期/Last Update: 2018-03-13