我正在阅读 Dijkstra 算法和 Floyd-Warshall 算法。我知道 Dijkstra 找到了从一个节点到所有其他节点的最佳路线，而 Floyd-Warshall 找到了所有节点配对的最佳路线。
我的问题是，如果我在每个节点上运行 Dijkstra 的算法以找到所有配对之间的最佳路线，它会比 Floyd 的算法更有效。
Dijkstra 的运行时间为 O(E + VlogV)，其中 Floyd 的运行时间为 O(V 3 )。如果 Dijkstra 失败，在这种情况下它的运行时间是多少？谢谢！
正如其他人指出的那样，Floyd-Warshall 运行时间 O(n 3 ) 并运行 Dijkstra 从每个节点到其他节点的搜索，假设您使用斐波那契堆来支持 Dijkstra 的实现，需要 O(mn + n 2日志 n)。但是，您不能始终在任意图上安全地运行 Dijkstra 算法，因为 Dijkstra 算法不适用于负边权重。
有一个真正卓越的算法，称为约翰逊算法，它是对从每个节点运行 Dijkstra 算法的轻微修改，即使图形包含负边（只要没有任何负循环），该方法也可以工作。该算法首先在图上运行Bellman-Ford以将其转换为没有负边的图，然后从每个顶点开始使用 Dijkstra 算法。因为 Bellman-Ford 运行时间为 O(mn)，所以整体渐近运行时间仍然是 O(mn + n 2 log n)，所以如果 m = o(n 2 )（注意这是n 的little-o），这方法比使用 Floyd-Warshall 渐近更快。
这里的一个问题是，这假设您拥有由斐波那契堆支持的 Dijkstra 算法。如果您没有可用的斐波那契堆并且不愿意投入 72 小时来构建、调试和测试一个堆，那么您仍然可以为 Dijkstra 算法使用二进制堆；它只是将运行时间增加到 O(m log n)，所以这个版本的 Johnson 算法在 O(mn log n) 中运行。这不再总是比 Floyd-Warshall 渐近更快，因为如果 m = Ω(n 2 )，那么 Floyd-Warshall 的运行时间为 O(n 3 )，而 Johnson 的算法运行时间为 O(n 3 log n)。然而，对于稀疏图，其中 m = o(n 2 / log n)，Johnson 算法的这种实现仍然渐近优于 Floyd-Warshall
简而言之：
希望这可以帮助！
在所有节点上运行 Dijkstra 的复杂度为 O(EV + V 2 logV)。当 E < V 2时，此复杂度低于 O(V 3 ) 。
这取决于。为所有节点运行 Dijkstra 给你O(VE + V^2log V)，而 Floyd 是O(V^3). 如果E = O(V^2)，那么两者在理论上是相同的，弗洛伊德在实践中更快。如果你E = O(V)，那么在理论上和实践上都更好地为所有节点运行 Dijkstra。
基本上，如果您希望拥有与您拥有的节点一样多的边，则从所有节点运行 Dijkstra，如果您希望拥有几乎完整的图，则运行 Floyd。
对于所有对最短路径，几乎没有 Floyd-Warshall 比 Dijkstra 更快（通常！！）