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