Floyd Warshall算法的时间复杂度

Question

Skiena的算法书包含以下对Floyd Warshall算法的解释:

 floyd(adjacency_matrix *g)
 {
   int i,j; /* dimension counters */
   int k; /* intermediate vertex counter */
   int through_k; /* distance through vertex k */
   for (k=1; k<=g->nvertices; k++)
       for (i=1; i<=g->nvertices; i++)
           for (j=1; j<=g->nvertices; j++) {
                through_k = g->weight[i][k]+g->weight[k][j];
                if (through_k < g->weight[i][j])
                      g->weight[i][j] = through_k;
           }
  }

Floyd-Warshall全对最短路径在O(n ³)时间内运行,这渐渐没有比n调用Dijkstra算法更好.但是,循环非常紧凑,程序太短,以至于在实践中运行得更好.值得注意的是,稀有图算法之一在邻接矩阵上比邻接列表更好.

有人可以详细说明为什么大胆的部分是真的吗？

Answer 1

让我们分解一下：

Floyd-Warshall 所有对最短路径在 O(n ³ ) 时间内运行......

这是因为我们有一个三重for循环，每个循环都有n次迭代

...渐近地不比对 Dijkstra 算法的 n 次调用好。...

回想一下，对 Dijkstra 算法的一次调用将告诉我们从一个特定节点x1到图中所有节点的所有最短路径。因此，我们可以对图中的所有节点对 Dijkstra 算法进行n 次调用：x1 , x2 , ... xn以找到从x1到所有节点、x2到所有节点、... xn到所有节点的最短路径。换句话说，这为我们提供了所有对最短路径——就像 Floyd Warshall 所做的那样！

Running Dijkstra n times:
time = number of nodes × O((n + e)lgn)      [assuming binary heap used for Dijkstra]
     = n × O((n + e)lgn)                
     = O(n(n + e)lgn)

因此，这是确实的情况下为O（n ^ 3）弗洛伊德-沃肖尔的时间不优于O（N（N + E）LGN）制作的时间ñ调用Dijkstra算法。

... 然而，循环如此紧凑，程序如此短，以至于它在实践中运行得更好。

这里的关键词是“在实践中”。请记住，渐近分析并不完美。这是性能的数学抽象/近似。当我们实际来运行代码时，有很多实际因素没有考虑到。处理器具有用于获取和运行指令的复杂低级架构。它流水线化指令、预取指令、尝试预测指令、缓存指令和数据，......这是非常不可预测的！然而，所有这些低级优化都会对算法的整体性能产生巨大影响。理论上较慢的算法可以获得提升，而理论上快速的算法可能不会获得相同的提升。这有时被称为大哦符号的隐藏常数因子。

事实证明，处理器喜欢优化嵌套for循环和多维数组！这就是斯基纳在这里暗指的。该for循环阵列使得物尽其用时间和空间局部性和工作以及与低级别的处理器优化。另一方面，Dijkstra 的算法也没有这样做，因此处理器优化也不起作用。因此，Dijkstra 在实践中确实可能会更慢。
Floyd-Warshall 是一个“短程序”，它没有使用任何复杂的数据结构，并且重复的指令数量很少。这些东西，连同处理器优化，都有助于 Floyd-Warshall 拥有一个小的隐藏常数因子。也就是说，³ )小。

Answer 2

然而，循环非常紧密，程序也很短，因此在实践中运行得更好。

如果您查看该算法，就会发现有 3 个循环，并且其中仅嵌套了 2 个语句。唯一的逻辑是在第三个嵌套循环内完成的。如果您运行 n Djikstra，逻辑将在第一个循环以及最后一个嵌套循环内完成，这很容易引起争议，不够干净。通过干净的三个循环，计算机也应该可以更轻松地管理内存。