基于最短增广链的最大流改进算法

网络最大流是经典的组合优化问题,它的经典算法主要有三种,分别是Ford-Fulkerson算法、最短增广链算法(Dinic算法)和预流推进算法。Ford-Fulkerson算法中由于增广链的选取任意性而有时无法得到理想的最大流。最短增广链算法在分层剩余网络中寻找最短增广链,从而避免了增广链选取的任意性。但最短增广链算法在求解最大流过程中每次增广都需要重新寻找最短增广链,利用率不高。针对这一问题,提出了一种修复最短增广链的新算法。该算法在沿最短增广链调整流量之后,删除最短增广链流量为零的弧,且寻找合适的路径修复最短增广链,从而提高了最短增广链的使用效率,减少了最短增广链的搜索次数。应用新算法进行了BA无标度网络建模仿真。实验结果表明,该算法运行效率要高于最短增广链算法。

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

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