On 01/29/2013 07:47 PM, Sirius Fuenmayor wrote:For unweigthed graphs the all-pairs-shortest-paths problem can be solved
> 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:
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.
This provides a logarithmic speedup of O(N*E / log N). Not a very
> Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523
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.
> <http://www.mimuw.edu.pl/~mucha/teaching/alp2006/seidel92.pdf>)
> 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
This is O(N^2.376 \log N), using fast matrix multiplication. Again, only
useful for the dense case.
I'm not aware of any implementation... It should be possible to
> Do you think it is plausible and possible to implement these
> algorithms? Any one have seen an implementation of these in any
> familiar language?
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