求解最小费用流的一种新算法

来源：计算机技术与发展杂志2018年第01期北京时间：

作者：纪亚劲;刘艳清;赵礼峰

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

关键词：最小费用流;Dijkstra 算法;余网络;ER 随机网络