All-Pairs Shortest-Paths Problem for Unweighted Graphs in O(n2 log n) Time

Authors: Udaya Kumar Reddy K. R, K. Viswanathan Iyer

Abstract:

Given a simple connected unweighted undirected graph G = (V (G), E(G)) with |V (G)| = n and |E(G)| = m, we present a new algorithm for the all-pairs shortest-path (APSP) problem. The running time of our algorithm is in O(n2 log n). This bound is an improvement over previous best known O(n2.376) time bound of Raimund Seidel (1995) for general graphs. The algorithm presented does not rely on fast matrix multiplication. Our algorithm with slight modifications, enables us to compute the APSP problem for unweighted directed graph in time O(n2 log n), improving a previous best known O(n2.575) time bound of Uri Zwick (2002).

Keywords: Distance in graphs, Dynamic programming, Graphalgorithms, Shortest paths.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334732

References:

[1] N. Alon, Z. Galil, and O. Margalit, "On the exponent of the all-pairs shortest path problem," J. Comput. Sys. Sci., vol. 54, pp. 255-262, 1997.
[2] T. M. Chan, "All-pairs shortest paths for Unweighted Undirected Graphs in o(mn) Time," In Proc. 17th annual ACM-SIAM Sympos. on Discrete Algorithms, pp. 514-523, 2006.
[3] F. F. Dragan, "Estimating all pairs shortest paths in restricted graph families: a unified approach," J. of Algorithms, vol. 57, pp. 1-21, 2005.
[4] T. Feder and R. Motwani, "Clique patritions, graph compression and speeding-up algorithms," J. Comput. Sys. Sci., vol. 51, pp. 261-272, 1995.
[5] Z. Galil and O. Margalit, "All pairs shortest distances for graphs with small integer length edges," Inf. Comput., vol. 134, pp. 103-139, 1997.
[6] Z. Galil and O. Margalit, "All pairs shortest paths for graphs with small integer length edges," J. Comput. Sys. Sci., vol. 54, pp. 243-254, 1997.
[7] R. Seidel, "On the all-pairs shortest path problem in unweighted undirected graphs," J. Comput. Sys. Sci., vol. 51, pp. 400-403, 1995.
[8] U. Zwick, "All-pairs shortest paths using bridging sets and rectangular matrix multiplication," J. ACM, vol. 49, pp. 289-317, 2002.