More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

In the first part of the paper, we reexamine the all-pairsshortest paths (APSP) problem and present a newalgorithm with running time approaching O(n3/log2n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors. 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(n3-(3-Ω)/(2d+4)), where Ω 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(n3-(3-Ω)/4)=O(n2.844) time) forAPSP in real-vertex-weighted graphs, as well as an improved result (near O(n(3+Ω)/2)=O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.