Performance of shortest path algorithms in network flow problems. (English) Zbl 0699.90031

Summary: It is known that minimum cost flow problems can be solved by successive augmentation 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.


90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI