Efficient Shortest Path Simplex Algorithms

Donald Goldfarb, Jianxiu Hao and Sheng-Roan Kai
Additional contact information
Donald Goldfarb: Columbia University, New York, New York
Jianxiu Hao: GTE Laboratories, Waltham, Massachusetts
Sheng-Roan Kai: GTE Laboratories, Waltham, Massachusetts

Operations Research, 1990, vol. 38, issue 4, 624-628

Abstract: We consider the specialization of the primal simplex algorithm to the problem of finding a tree of directed shortest paths from a given node to all other nodes in a network of n nodes or finding a directed cycle of negative length. Two efficient variants of this shortest path simplex algorithm are analyzed and shown to require at most ( n − 1)( n − 2)/2 pivots and O ( n 3 ) time.

Keywords: networks/graphs; distance algorithms: shortest path algorithms; programming; integer applications: simplex algorithms for shortest path problems (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.4.624 (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:oropre:v:38:y:1990:i:4:p:624-628

Access Statistics for this article

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