More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

摘要

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~2 n), 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?ω)/(2d+4))), where ω