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 <[email protected]>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. > > > (https://www.waset.org/journals/ijcms/v3/v3-5-43.pdf) > > 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 <[email protected]> > > > _______________________________________________ > graph-tool mailing list > [email protected] > http://lists.skewed.de/mailman/listinfo/graph-tool > >
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
