A new approach to all-pairs shortest paths on real-weighted graphs

AbstractWe present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. It runs in O(mn+n2loglogn) time, improving on the long-standing bound of O(mn+n2logn) derived from an implementation of Dijkstra's algorithm with Fibonacci heaps. Here m and n are the number of edges and vertices, respectively.Our algorithm is rooted in the so-called component hierarchy approach to shortest paths invented by Thorup for integer-weighted undirected graphs, and generalized by Hagerup to integer-weighted directed graphs. The technical contributions of this paper include a method for approximating shortest path distances and a method for leveraging approximate distances in the computation of exact ones. We also provide a simple, one line characterization of the class of hierarchy-type shortest path algorithms. This characterization leads to some pessimistic lower bounds on computing single-source shortest paths with a hierarchy-type algorithm