12

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 3 ) 时间内运行，这在渐近上并不比对 Dijkstra 算法的 n 次调用更好。但是，循环非常紧凑，程序非常短，以至于它在实践中运行得更好。值得注意的是，它是一种罕见的图算法，它在邻接矩阵上比邻接列表工作得更好。

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

4

4 回答 4

10

让我们分解一下：

Floyd-Warshall 全对最短路径在 O(n 3 ) 时间内运行...

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

...这并不比对 Dijkstra 算法的 n 次调用更好。...

回想一下，对 Dijkstra 算法的一次调用将告诉我们从一个特定节点x1到图中所有节点的所有最短路径。因此，我们可以对图中的所有节点进行n次 Dijkstra 算法调用：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)

因此，Floyd-Warshall 的O(n^3)时间并不比调用 Dijkstra的 O( n (n + e)lgn)时间好。

...但是，循环非常紧凑，程序非常短，以至于在实践中运行得更好。

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

事实证明，处理器喜欢优化嵌套for循环和多维数组！这就是 Skiena 在这里所暗示的。数组的for循环充分利用了时间和空间的局部性，并与低级处理器优化配合得很好。另一方面，Dijkstra 的算法不能很好地做到这一点，因此处理器优化也不能很好地工作。因此，Dijkstra 在实践中确实可能会更慢。
Floyd-Warshall 是一个“短程序”，它不使用任何复杂的数据结构并且重复的指令数量很少。这些东西，连同处理器优化一起，导致 Floyd-Warshall 有一个小的隐藏常数因子。也就是说，3 )体积小。

于 2018-04-14T20:06:01.717 回答
4

假设 v 为顶点数。对于稀疏图（少数边），边数e = O(v)。对于密集图（许多边）e = O(v^2)。

现在，单一来源的最短路径问题的最佳渐近实现需要摊销时间。Dijkstra 算法的这种实现使用了斐波那契堆，由于涉及的常量值很高，因此不太实用。例如，除了父节点和子节点之外，堆中的每个顶点也使用双链表连接到其兄弟节点。这导致每个节点存储大量指针。除了堆之外，甚至每个顶点都需要访问邻接表。O(e + vlogv)

如果我们假设我们的图是密集图的最坏情况，e = O(v^2)，Dijkstra 的算法将采用O(v^2 + vlogv)= O(v^2)。现在你将如何找到所有顶点对之间的最短路径？

选项1：

您可以使用Dijkstra 的算法并将其应用于每个 vertex。

那要花多少钱？v * O(v^2) = O(v^3)。但是，所涉及的常数会使实际成本更高。您必须构建堆（一次），检查邻接列表，减少键并提取每个顶点的最小值（同时保持最小堆）。

选项 2：

Floyd-Warshall 算法基本上适用于 av * v 邻接矩阵。它会考虑每个顶点，并决定如果您可以通过该顶点，那将是更短的路线。这是对矩阵的所有 v^2 元素执行的恒定时间比较和插入操作（到 2D 数组中）。

这需要对每个顶点执行。因此，时间复杂度为O(v^3)，但具有非常小的常数值，使其在实现过程中非常可行。

因此，您只需要一个邻接矩阵格式的图形，一个存储新值的邻接矩阵和 3 个嵌套的 for 循环，总共运行 v * v * v 次。我猜这就是紧凑和简单的意思！

于 2017-11-26T14:58:25.743 回答
3

但是，循环非常紧凑，程序非常短，以至于它在实践中运行得更好。

如果您查看该算法，则会发现有 3 个循环，其中只有 2 个语句嵌套在其中。唯一的逻辑是在第三个嵌套循环中完成的。如果您运行 n Djikstra's，逻辑将在第一个循环以及最后一个嵌套中完成，这很容易争论不干净。使用干净的三个循环，计算机也应该可以更轻松地管理内存。

于 2012-05-28T03:57:38.777 回答
2

Dijkstra 的算法具有常见的数据结构是 O(E log v)，但 Fibonacci heap 将其改进为 O(E+v log v)，这是更复杂的数据结构，并且算法的常量工厂比 floyed 更大。查看此链接中的运行时间。

这个问题的差异与 q-sort 和 heap-sort 之间的差异相同

于 2012-05-28T14:58:49.640 回答