计算图的传递闭包需要的Asymtotic运行时间？

Question

图的传递闭包在此处定义:http://mathworld.wolfram.com/TransitiveClosure.html

在O(n ^ 3)中很容易实现,其中n是顶点的数量.我想知道它是否可以及时完成O(n ^ 2).

Answer 1

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