An O(nm)-time network simplex algorithm for the shortest path problem
成果类型：
Article
署名作者：
Goldfarb, D; Jin, ZY
署名单位：
Columbia University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.3.445
发表日期：
1999
页码：
445-448
关键词：
摘要：
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.