An O(n 3 log log n/ log2 n) Time Algorithm for All Pairs Shortest Paths
Degree GrantorUniversity of Canterbury
Given an input directed graph G = (V, E), the all pairs shortest path problem (APSP) is to compute the shortest paths between all pairs of vertices of G assuming that edge costs are real values. The APSP problem is a fundamental problem in computer science and has received considerable attention. Early algorithms such as Floyd’s algorithm (, pp. 211-212) computes all pairs shortest paths in O(n 3 ) time, where n is the number of vertices of the graph. Improved results show that all pairs shortest paths can be computed in O(mn+n 2 log n) time , where m is the number of edges of the graph. Pettie showed  an algorithm with time complexity O(mn+n 2 log log n). See  for recent development. There are also results for all pairs shortest paths for graphs with integer weights[10, 16, 17, 21– 23]. Fredman gave the first subcubic algorithm  for all pairs shortest paths. His algorithm runs in O(n 3 (log log n/ log n) 1/3 ) time. Fredman’s algorithm can also run in O(n 2.5 ) time nonuniformly. Later Takaoka improved the upper bound for all pairs shortest paths to O(n 3 (log log n/ log n) 1/2 ) . Dobosiewicz  gave an upper bound of O(n 3/(log n) 1/2 ) with extended operations such as normalization capability of floating point numbers in O(1) time. Earlier Han obtained an algorithm with time complexity O(n 3 (log log n/ log n) 5/7 ) . Later Takaoka obtained an algorithm with time O(n 3 log log n/ log n)  and Zwick gave an algorithm with time O(n 3√ log log n/ log n) . Chan gave an algorithm with time complexity of O(n 3/ log n) . Chan’s algorithm does not use tabulation and bit-wise parallelism. His algorithm also runs on a pointer machine.