All pairs shortest path in undirected and unweighted graphs

Question

I'm aware that the single source shortest path in a undirected and unweighted graph can be easily solved by BFS.

For the case of the all pairs shortest path problem, is there any better solution than running a BFS for each node?

Answer 1

I have no idea why this question was considered off-topic for CSTheory. Certainly this question is very interesting to those who work in graph algorithms.

To that group, asking if there is a better solution to APSP than running BFS from each node, is equivalent to asking if there is an algorithm that runs in asymptotically less than $O(mn+n^2)$ time where $m$ is the number of edges and $n$ is the number of nodes. It is a major open problem to improve significantly on this running time.

Timothy Chan found some small algorithmic improvements in SODA'06 that may have promise in practice (he implemented them). See the paper:

Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523

In the undirected and unweighted case, one can solve the problem via reductions to matrix multiplication of $n \times n$ matrices (so theoretically, this means you can get $n^{2.376}$ time). If your graph is dense then this could be very useful. These algorithms are rather ingenious:

Zvi Galil, Oded Margalit: All Pairs Shortest Distances for Graphs with Small Integer Length Edges. Inf. Comput. 134(2): 103-139 (1997)

Zvi Galil, Oded Margalit: All Pairs Shortest Paths for Graphs with Small Integer Length Edges. J. Comput. Syst. Sci. 54(2): 243-254 (1997)

Raimund Seidel: On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. J. Comput. Syst. Sci. 51(3): 400-403 (1995)

Hopefully, expositions of the last three (or the papers themselves) can be found freely on the Web.

Answer 2

I had to write a fast implementation of this to deal with large graphs, and I found the n BFS to be much better than the Floyd-Warshall algorithm. Their way of storing the results, though (a matrix of predecessors) remains a very good way to store the result ! way better than storing $\binom n 2$ paths (even when they are short) -- especially for compact use of memory.

Nathann

Answer 3

It may be possible to find all shortest paths (only distances) in $O(n^2 log\ n)$ time and $O(n^2)$ space if following paper is true:

Udaya Kumar Reddy K. R, and K. Viswanathan Iyer: All-pairs shortest-paths problem for unweighted graphs in $O(n^2 log\ n)$ time
World Academy of Science, Engineering and Technology Vol:3 (2009)

Note that World Academy of Science is considered predatory, so I would say you need to check carefully that paper if it's actually true.