An O(nm)-time network simplex algorithm for the shortest path problem

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