External-memory exact and approximate all-pairs shortest-paths in undirected graphs
Rezaul Chowdhury, Vijaya Ramachandran · 2005
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 algorithnls with O(V. ~ log. ~ ~) I/Os, where B is the block-size and M is the size of internal memory. For weighted tmdirected graphs we present a cache-aware APSP algorithm that performs O(V. ( V/ ~ + ~ log ~)) 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 C9(V + E) extra space, and all of our other algorithms use O(V 2) space. 1