External-memory exact and approximate all-pairs shortest-paths in undirected graphs

We present several new external-memory algorithms for finding all-pairs shortest paths in a V-node, E-edge undirected graph. For all-pairs shortest paths and diameter in unweighted undirected graphs we present cache-oblivious algorithms with O(V · E/B log _M/B E/B) I/Os, where B is the block-size and M is the size of internal memory. For weighted undirected graphs we present a cache-aware APSP algorithm that performs O (V · (√V E/B + E/B log E/B)) I/Os. We also present efficient cacheaware algorithms that find paths between all pairs of vertices in an unweighted graph with lengths within a small additive constant of the shortest path length. All of our results improve earlier results known for these problems, For approximate APSP we provide the first nontrivial results. Our diameter result uses O(V + E) extra space, and all of our other algorithms use O(V ²) space.