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

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.


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.)
Full Text: DOI