An O(nm)-Time Network Simplex Algorithm for the Shortest Path Problem

Donald Goldfarb and Zhiying Jin
Additional contact information
Donald Goldfarb: Columbia University, New York, New York
Zhiying Jin: GTE Laboratories, Inc., Waltham, Massachusetts

Operations Research, 1999, vol. 47, issue 3, 445-448

Abstract: We present an O ( nm )-time network simplex algorithm for finding a tree of shortest paths from a given node to all other nodes in a network of n nodes and m directed arcs or finding a directed cycle of negative length. The worst-case running time of this algorithm is as fast as that proved for any strongly polynomial algorithm and faster than that proved for any previously proposed simplex algorithm for this problem. We also show that this algorithm can be implemented in O ( nlogn ) time using O (( m / logn ) + n ) exclusive read–exclusive write processors of a parallel random access machine.

Keywords: networks/graphs; distance algorithms; general shortest paths; programming; linear algorithms; network simplex; analysis of algorithms; computational complexity; strongly polynomial (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.3.445 (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:47:y:1999:i:3:p:445-448

Access Statistics for this article

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