Categories and Subject Descriptors F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems General Terms Algorithms, Theory

ABSTRACT In the first part of the paper, we reexamine the all-pairs shortest paths (APSP) problem and present a new algorithm with running time approaching O(n3 / log2 n), which improves all known algorithms for general real-weighted dense graphs and is perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors