algorithm - 有向图最著名的传递闭包算法是什么？

Question

就运行时而言，有向图最著名的传递闭包算法是什么？

我目前使用的是 Warshall 算法，但它的复杂度为 O(n^3)。虽然，由于图形表示，我的实现稍微好一些(而不是检查所有边，它只检查所有出边)。有没有比这更好的传递闭包算法？特别是，是否有专门针对共享内存多线程架构的内容？

Answer 1

本文讨论了各种传递闭包算法的性能:

http://www.vldb.org/conf/1988/P382.PDF

论文中的一个有趣想法是避免在图形发生变化时重新计算整个闭包。

Esko Nuutila 也有这个页面，其中列出了一些最新的算法:

http://www.cs.hut.fi/~enu/tc.html

该页面上列出的他的博士论文可能是最好的起点:

http://www.cs.hut.fi/~enu/thesis.html

从那个页面:

The experiments also indicate that with the interval representation and the new algorithms, the transitive closure can be computed typically in time linear to the size of the input graph.