最大动态流关键弧的改进算法

Improved algorithm for vital arc of maximum dynamic flow

针对时间容量网络的最大动态流的关键弧问题,首先分析了经典的Ford-Fulkerson最大动态流算法,在此基础上简化了最大动态流算法,并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法。算法将计算新网络最大动态流时共有的最小费用路保留,去掉了自然算法中重复的计算。与自然算法进行对比分析,结果表明改进算法比自然算法的效率更高。

For the vital arc problem of maximum dynamic flow in time-capacitated network,the classic Ford-Fulkerson maximum dynamic flow algorithm was analyzed and simplified.Thus an improved algorithm based on minimum cost augmenting path to find the vital arc of the maximum dynamic flow was proposed.The shared minimum augmenting paths were retained when computing maximum dynamic flow in new network and the unnecessary computation was removed in the algorithm.Finally,the improved algorithm was compared with the original algorithm and natural algorithm.The numerical analysis shows that the improved algorithm is more efficient than the natural algorithm.