All-pairs shortest paths for unweighted undirected graphs in o(mn) time
Timothy M. Chan · 2006
Abstract We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times: O(mn = log n) if m? n log