有向网络中无环最小饱和流问题及其算法

假设网络的初始流为零流,以最大堵塞截面为准堵塞截面,找出从源点到汇点的包含准堵塞截面弧最多的有条件最长增广路对网络进行增流,直至网络达到饱和,并对该算法进行了复杂性分析。利用该算法对多个网络进行论证,结果表明利用有条件最长增广路算法计算出的最小饱和流值与仿真计算以及与双向增流算法计算得到的结果基本相同,增流次数大大减少,且求解的结果避免了在封闭环路中的流量流动,进一步优化了最小饱和流值。

Minimum Saturated Flow Problem in Directed Network and Its Algorithm

The initial flow of the network is supposed to be the zero and the maximum blocking-cutest to be the quasi-blocking-cutest.The longest augmented path is chosen from the source to the sink,in which the number of the arcs of the quasi-blocking-cutest is the most.The flow along the augmented path in the network is added until the network reaches saturation.The related complexity of the algorithm is also presented.Comparied with some network examples,the minimum saturated flow can share the same value with the simulation and the two-way flow-augmenting algorithm.The algorithm can use the less time to obtain the minimum saturated flow.The resolved results avoid the flow in the closed ring of the network.Thus the minimum saturated flow is further optimized.