Comparison of Parallel APSP Algorithms.pdf

Comparison of Parallel APSP AlgorithmsBenjamin Diament, Andras FerenczMay 21, 19991 IntroductionThe All Pairs Shortest Path (APSP) problem has been widely studied in theoretical computer sci-ence. It arises directly from practical applications and as a subroutine of more complex algorithms.Large instances can be found in everything from large detailed geographical maps to wide areanetwork (e.g. Internet) connectivity graphs. Since the best-known serial algorithms for the densecase require O(n3) time, serial computation is infeasible for these large inputs.Given a graph G = (V;E), the APSP problem is to nd dij for for all i; j 2 V , where dij is thelength of the shortest simple path from i to j.Several well known algorithms have been developed for APSP, each applicable for specialized in-stances of the problem. One class of these uses Dijkstras single-source shortest-paths algorithm.A single run of Dijkstras algorithm takes O(jV j2) for dense and O(jEj log jV j) for sparse graphs ifthe priority queue needed in the algorithm is implemented as a binary heap, or O(jV j log jV j+ jEj)if a Fibonacci heap is used instead. This can be applied to the APSP problem by running itfrom each node independently (Call this algorithm AP-Dijkstra), achieving a running time ofO(jV j
CostDijkstra). This algorithm is trivially parallelizable for up to jV j processors, whereeach processor is assigned jV jp vertices on which to run Dijkstras algorithm. While no communica-tion is required for AP-Dijkstra, it works only for graphs with positive edge weights. Furthermore,its implementation may be very complex (especially if the optimal Fibonacci heaps are to be used),and it exhibits poor cache performance, since the inner loop includes many pointer dereferences.A preferred alternative was originally developed by Floyd and Warshall, and is similar in avor tomatrix multiplication. It runs in time O(jV j3), the same as AP-Dijkstra for dense graphs, but inpractice has better better cache per