algorithm - Dijkstra 与 Floyd-Warshall : Finding optimal route on all node pairs

Question

我正在阅读 Dijkstra 算法和 Floyd-Warshall 算法。我知道 Dijkstra 找到了从一个节点到所有其他节点的最佳路径，而 Floyd-Warshall 找到了所有节点配对的最佳路径。

我的问题是，如果我在每个节点上运行 Dijkstra 的算法以找到所有配对之间的最佳路径，Dijkstra 的算法是否会比 Floyd 的算法更有效。

Dijkstra 的运行时间是 O(E + VlogV)，而 Floyd 的是 O(V³)。如果 Dijkstra 失败，在这种情况下它的运行时间是多少？谢谢!

Answer 1

正如其他人所指出的，Floyd-Warshall 的运行时间为 O(n³) 并运行从每个节点到其他节点的 Dijkstra 搜索，假设您使用斐波那契堆来支持您的 Dijkstra 实现需要 O(mn + n² log n)。但是，您不能总是在任意图上安全地运行 Dijkstra 算法，因为 Dijkstra 算法不适用于负边权重。

有一个真正非凡的算法叫做 Johnson's algorithm 这是对从每个节点运行 Dijkstra 算法的轻微修改，即使图形包含负边(只要不存在任何负循环)，该方法也能正常工作。该算法通过首先运行 Bellman-Ford 来工作在图上将其转换为没有负边的图，然后从每个顶点开始使用 Dijkstra 算法。因为 Bellman-Ford 运行时间为 O(mn)，整体渐近运行时间仍然是 O(mn + n² log n)，所以如果 m = o(n² )(请注意，这是 n 的 little-o)，这种方法比使用 Floyd-Warshall 渐近地快。

这里的一个问题是，这假设您拥有由斐波那契堆支持的 Dijkstra 算法。如果您没有可用的 Fibonacci 堆并且不愿意花费 72 小时来构建、调试和测试一个堆，那么您仍然可以对 Dijkstra 算法使用二进制堆；它只是将运行时间增加到 O(m log n)，所以这个版本的 Johnson 算法运行时间为 O(mn log n)。这不再总是比 Floyd-Warshall 渐近更快，因为如果 m = Ω(n²) 那么 Floyd-Warshall 的运行时间为 O(n³) 而 Johnson 的算法运行在 O(n³ log n) 中。然而，对于稀疏图，其中 m = o(n²/log n)，Johnson 算法的这种实现在渐进方面仍然优于 Floyd-Warshall

简而言之:

• 对于 Fibonacci 堆，Johnson 的算法总是渐进地至少与 Floyd-Warshall 一样好，尽管它更难编写代码。
• 对于二叉堆，Johnson 算法通常渐近性至少与 Floyd-Warshall 一样好，但在处理大型密集图时不是一个好的选择。

希望这对您有所帮助!