An O(nm)-Time Network Simplex Algorithm for the Shortest Path Problem
Operations Research · 1999 · Volume 47 · Issue 3
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
Enable JavaScript for citation tools and additional paper interactions.