Scaling algorithms for the shortest paths problem. (English) Zbl 0831.68046

Goldberg, Andrew V.

SIAM J. Comput. 24, No. 3, 494-504 (1995).

Summary: We describe a new method for designing scaling algorithms for the single- source shortest paths problem and use this method to obtain an \(O (\sqrt nm \log N)\) algorithm for the problem. (Here \(n\) and \(m\) are the number of nodes and arcs in the input network and \(N\) is essentially the absolute value of the most negative arc length: arc lengths are assumed to be integral.) This improves previous bounds for the problem. The method extends to related problems.

MSC:

68W10	Parallel algorithms in computer science
68Q25	Analysis of algorithms and problem complexity
68R10	Graph theory (including graph drawing) in computer science
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

scaling algorithms; shortest paths problem