Scaling Algorithms for the Shortest Paths Problem
Andrew V. Goldberg · SIAM Journal on Computing · 1995
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.