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:[EQUATION]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 ＆Lt;问题均已知的最佳时限。 n 1.376 。对于未加权有向图的直径问题，我们还获得了类似类型的结果。
展开▼
