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> nlog nlog log log n O(mnlog log n/ log n) ifm> nlog log n O(n2 log2 log n/ log n) ifm≤ nlog log n. These represent the best time bounds known for the problem for all m? n1.376.We also obtain a similar type of result for the diameter problem for unweighted directed graphs.
展开▼
机译：我们重新讨论具有n个顶点和m个边的无权无向图的全对最短路径问题。我们提出了具有以下运行时间的新算法：如果m> nlog nlog log log n O（mnlog log n / log n）ifm> nlog log n O（n2 log2 log n / log n）ifm，则O（mn / log n） ≤nlog log n。这些代表了所有m？问题已知的最佳时限。 n1.376。对于非加权有向图的直径问题，我们也获得了类似的结果。
展开▼
