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.

> (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 <tiago@skewed.de>


_______________________________________________
graph-tool mailing list
graph-tool@skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool