All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time

作者：Chan Timothy M^*

来源：ACM Transactions on Algorithms, 2012, 8(4): 34.

DOI：10.1145/2344422.2344424

• Algorithms
• Theory
• Graph algorithms
• shortest paths
• word RAM

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: %26lt;br%26gt;{ O(mn/log n) if m %26gt; n log n log log log n O(mn log log n/log n) if m%26gt; n log log n O(n2log2logn/logn) if m %26lt;= n log log n. %26lt;br%26gt;These represent the best time bounds known for the problem for all m %26lt;%26lt; n(1.376). We also obtain a similar type of result for the diameter problem for unweighted directed graphs.

• 出版日期2012-9