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?

  • 2
    $\begingroup$ Standard books in algorithms cover various efficient algorithms for all-pairs shortest path. $\endgroup$ – MCH Aug 17 '11 at 21:24
  • 1
    $\begingroup$ Can you cite any of those standard books in algorithms? Thanks! $\endgroup$ – aromero Aug 17 '11 at 23:26
  • $\begingroup$ @aromero, this question is off-topic for cstheory, please refer to FAQ to understand the scope of cstheory. I am closing the question as off-topic and migrating it to Math.SE. $\endgroup$ – Kaveh Aug 18 '11 at 0:45
  • 3
    $\begingroup$ FWIW, nowadays questions such as this are ontopic on Computer Science. $\endgroup$ – Raphael Sep 17 '14 at 15:50

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.

| cite | improve this answer | |
  • $\begingroup$ Great answer, thanks $\endgroup$ – aromero Aug 18 '11 at 19:55

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.


| cite | improve this answer | |
  • $\begingroup$ You are right, the storing of results is also relevant to note. Thanks $\endgroup$ – aromero Aug 18 '11 at 19:58

It is possible to find all shortest paths (only distances) in $O(n^2 log\ n)$ time and $O(n^2)$ space.

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)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.