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