## An O(n 3 log log n/ log2 n) Time Algorithm for All Pairs Shortest Paths

##### View/Open

##### Author

##### Date

2002##### Permanent Link

http://hdl.handle.net/10092/14770##### Degree Grantor

University of Canterbury##### Degree Level

Doctoral##### Degree Name

OtherGiven 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 ([2], 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 [9], where m is the number of edges of the graph. Pettie showed [14] an algorithm with time complexity O(mn+n 2 log log n). See [15] 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 [8] 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 ) [19]. Dobosiewicz [7] 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 ) [12]. Later Takaoka obtained an algorithm with time O(n 3 log log n/ log n) [20] and Zwick gave an algorithm with time O(n 3√ log log n/ log n) [24]. Chan gave an algorithm with time complexity of O(n 3/ log n) [6]. Chan’s algorithm does not use tabulation and bit-wise parallelism. His algorithm also runs on a pointer machine.