More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

Abstract

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time $O(n^3\log^3\log n/\log^2n)$, which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of “geometrically weighted” graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near $O(n^{3-(3-\omega)/(2d+4)})$, where $\omega<2.376$; in two dimensions, this is $O(n^{2.922})$. Our framework greatly extends the previously considered case of small–integer-weighted graphs, and incidentally also yields the first truly subcubic result (near $O(n^{3-(3-\omega)/4})=O(n^{2.844})$ time) for APSP in real–vertex-weighted graphs, as well as an improved result (near $O(n^{(3+\omega)/2})=O(n^{2.688})$ time) for the all-pairs lightest shortest path problem for small–integer-weighted graphs.