This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Goldfarb, D. Articles by Jin, Z. Search for Related Content

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

Columbia University, New York, New York
GTE Laboratories, Inc., Waltham, Massachusetts

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.

Subject classifications: networks/graphs; distance algorithms; general shortest paths; programming; linear algorithms; network simplex; analysis of algorithms; computational complexity; strongly polynomial.

This article has been cited by other articles:

				I-L. Wang, E. L. Johnson, and J. S. Sokol A Multiple Pairs Shortest Path Algorithm Transportation Science, November 1, 2005; 39(4): 465 - 476. [Abstract] [PDF]