After reading this I agree that it is better to use just N bfs, Thanks for taking the time to give a detailed explanation. On Wed, Jan 30, 2013 at 7:06 AM, Tiago de Paula Peixoto <tiago@skewed.de>wrote:
On 01/29/2013 07:47 PM, Sirius Fuenmayor wrote:
If I understand correctly the Floyd-Warshall and Johnson’s algorithms are only useful in weighted graphs, so I was looking for algorithms to compute the all-pairs-shortest-paths for unweighted and undirected graphs fastest than the usual breadth-first search (BFS) method, and I found these algorithms:
For unweigthed graphs the all-pairs-shortest-paths problem can be solved with N BFS searches, which correspond to a complexity of O(N^2 + N*E), or simply O(N^2) for sparse graphs. It is unlikely to exist a much better bound, since there are O(N^2) distances which need to be computed in the first place... For the dense case, the complexity becomes O(N^3), and I believe the majority of improvements deal with this case.
Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523
This provides a logarithmic speedup of O(N*E / log N). Not a very dramatic improvement. For the sparse case they actually promise O(N^2 (log^2log N) / log N), which would be an improvement over BFS. However the algorithm seems quite complicated, and it is quite likely that it will be slower than simple BFS, unless the value of N is much larger than what is encountered in practice.
This is actually another paper, with O(N^2 log N). Its worse than BFS for the sparse case.
Raimund Seidel: On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. J. Comput. Syst. Sci. 51(3): 400-403 (1995) (www.mimuw.edu.pl/~mucha/teaching/alp2006/seidel92.pdf <http://www.mimuw.edu.pl/~mucha/teaching/alp2006/seidel92.pdf>)
This is O(N^2.376 \log N), using fast matrix multiplication. Again, only useful for the dense case.
Do you think it is plausible and possible to implement these algorithms? Any one have seen an implementation of these in any familiar language?
I'm not aware of any implementation... It should be possible to implement them, but they seem to provide benefits only in the dense case. However, I don't think it is worth the effort for the vast majority of cases when APSP is needed.
Cheers, Tiago
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool