Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Aug 18 '11 at 0:45

This question came from our site for theoretical computer scientists and researchers in related fields.

2  
Standard books in algorithms cover various efficient algorithms for all-pairs shortest path. –  MCH Aug 17 '11 at 21:24
    
Can you cite any of those standard books in algorithms? Thanks! –  aromero Aug 17 '11 at 23:26
    
@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. –  Kaveh Aug 18 '11 at 0:45
add comment

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
    
Great answer, thanks –  aromero Aug 18 '11 at 19:55
add comment

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

share|improve this answer
    
You are right, the storing of results is also relevant to note. Thanks –  aromero Aug 18 '11 at 19:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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