网络最小费用流问题是经典的双目标优化问题,其中利用的图论方法主要有负费用回路算法和最小费用路算法.最小费用路(Busacker-Gowan)算法每次增广流值之前都需要搜索一次最小费用路径,导致算法复杂度偏高,并且该算法是在剩余网络的基础上进行增广,使得该算法在计算预定流值最小费用流时有点冗余.针对这些不足,提出了一种求最小费用流的新算法.该算法首先利用改进的Dijkstra算法一次搜索出所有的源点至汇点费用路径,并且在余网络中增广流值.由于余网络比剩余网络构造简单,所以最终提高了算法的时间效率.仿真实验表明,在ER随机网络中提出算法和经典算法的计算结果相同,并且提出算法不管是在稀疏网络还是非稀疏网络中其运行时间比经典算法都要少,同时更适用于稀疏网络.%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.
展开▼
