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:
Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523 (https://www.waset.org/journals/ijcms/v3/v3-5-43.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) Do you think it is plausible and possible to implement these algorithms? Any one have seen an implementation of these in any familiar language?
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
