language-agnostic - 计算图的传递闭包所需的渐近运行时间？

Question

图的传递闭包定义为 e。 G。这里:http://mathworld.wolfram.com/TransitiveClosure.html

在 O(n^3) 中很容易实现，其中 n 是顶点数。我想知道是否可以在 O(n^2) 时间内完成。

Answer 1

不。我认为它没有 O(n2) 算法。我希望如果存在这样的算法，您也可以解决 O(n2) 中的所有对最短路径问题，但事实并非如此。我能想到的渐近最快的算法是 Dijkstra 最短路径算法的实现，带有斐波那契堆(O(n2log n) 在不是非常密集的图中)。