Performance of Shortest Path Algorithms in Network Flow Problems

James J. Divoky and Ming S. Hung
Additional contact information
James J. Divoky: College of Business Administration, University of Akron, Akron, Ohio 44325
Ming S. Hung: Graduate School of Management, Kent State University, Kent, Ohio 44242

Management Science, 1990, vol. 36, issue 6, 661-673

Abstract: 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.

Keywords: shortest path; empirical testing (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.36.6.661 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:36:y:1990:i:6:p:661-673

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().