23
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ Standard books in algorithms cover various efficient algorithms for all-pairs shortest path. $\endgroup$
    – MCH
    Commented Aug 17, 2011 at 21:24
  • 1
    $\begingroup$ Can you cite any of those standard books in algorithms? Thanks! $\endgroup$
    – aromero
    Commented Aug 17, 2011 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
    Commented Aug 18, 2011 at 0:45
  • 4
    $\begingroup$ FWIW, nowadays questions such as this are ontopic on Computer Science. $\endgroup$
    – Raphael
    Commented Sep 17, 2014 at 15:50

3 Answers 3

30
$\begingroup$

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.

$\endgroup$
0
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You are right, the storing of results is also relevant to note. Thanks $\endgroup$
    – aromero
    Commented Aug 18, 2011 at 19:58
1
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ WASET is a predatory publisher and not a trusted source for scientific publications: en.wikipedia.org/wiki/… $\endgroup$ Commented Nov 4, 2019 at 16:13
  • 1
    $\begingroup$ @StefanNeubert Didn't know it is the case. Thanks for noting! $\endgroup$
    – Somnium
    Commented Jun 22, 2022 at 11:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .