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 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.