Performance of Shortest Path Algorithms in Network Flow Problems
研究在网络流问题中实现最短路径算法的具体问题，特别关注流网络的动态拓扑结构，开发了能模拟这种拓扑的网络生成器，并通过9000个测试问题比较不同策略和算法组合的性能。
It is known that minimum cost flow problems can be solved by successive augmentations along shortest paths. In this paper the issues of implementing shortest path algorithms in this context are examined. Of particular interest is the dynamic topology that the flow networks exhibit. We develop a network generator capable of emulating such topology. Strategies for exploiting the special structures in such networks are discussed. A set of 9000 test problems is offered, from which a particular strategy/algorithm combination is shown to consistently produce superior results when compared to the other combinations.