计算机技术与发展2018，Vol.28Issue(1)：108-111,115,5.DOI:10.3969/j.issn.1673-629X.2018.01.023
求解最小费用流的一种新算法
A New Algorithm for Solving Minimum Cost Flow
摘要
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 algo-rithm 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.关键词
最小费用流/Dijkstra算法/余网络/ER随机网络Key words
minimum cost flow/Dijkstra algorithm/remainder network/ER stochastic network分类
信息技术与安全科学引用本文复制引用
纪亚劲,刘艳清,赵礼峰..求解最小费用流的一种新算法[J].计算机技术与发展,2018,28(1):108-111,115,5.基金项目
国家自然科学基金青年基金项目(61304169) （61304169）
