计算有向图的传递闭包所需的渐进运行时间是多少？

Question

7

当顶点数为n时，可以很容易地在O(n^3)的时间内完成。我想知道是否可以在O(n^2)的时间内完成。

- Niko

3个回答

1

嗯，我找到了一个计算传递闭包的算法，其预期运行时间为O(n^2)。

- Niko

使用哪种随机分布？ - jpalecek

我不知道。我不想使用它，因为我不想在我的周围算法中引入任何随机性。链接在这里：http://www.springerlink.com/content/f511w61n62l17168/ - nes1983

1

鉴于这个问题：

你能想出一个O(kn^2 + m)的传递闭包/约简算法吗？其中k是传递闭包/约简中缺失/额外边的数量？

对于那些比我们更多思考这些问题的人来说，这仍然被认为是一个未解决的问题，我会说“我不知道”。

（但如果你解决了它并想要获得博士学位，我知道那个算法。）

- MarkusQ

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mehrdad · Accepted Answer

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