shortest-path - DAG（有向无环图）中的所有最短路径

Question

我有一个加权 DAG，带有一些负边权重，并且想在其中找到所有最短路径。有没有比 O(n^2) 复杂度更好的算法。（我的图是完整的，即对于 {1..n} 中的任何 i,j 和 i < j 都有一条边 (i,j)。

谢谢

Answer 1

好吧，一种流行的寻路算法是 A*。但是您可以查看这篇文章以获取更多信息：

转到文章

干杯

Answer 2

您正在寻找的算法是Floyd-Warshall，它在 O(n ³ ) 中运行。

有时你可以通过在每个节点上运行 Djikstra 来做得更好。使用斐波那契堆，您可以获得 O(n ² log n + ne)，其中 e = 边数。甚至可以让它与负边权重一起使用！

然而，斐波那契堆有很大的常数，所以在实践中，这种方法只会对非常稀疏的图更快。既然您说您的图表是完整的，那么 Floyd-Warshall 是您最好的选择。