1

是否有一个简单的解释来解释为什么这个片段找到两个顶点之间的最短距离

for (k = 0; k < n; ++k)
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

而这并没有 

for (i = 0; i < n; ++i)
  for (j = 0; j < n; ++j)
    for (k = 0; k < n; ++k)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

（因为 k 是第二个片段中最里面的一个）

4

4 回答 4

4

k因为这个想法是通过在每一步尝试通过节点来尝试使路径更好，以改进每条i - j路径。

符号无关紧要，您可以根据需要i, j, k用作循环变量k, i, j，但您必须牢记上述逻辑。在这种情况下，您将需要尝试j - k通过i每一步来改进路径：

for i = 0, n
  for j = 0, n
    for k = 0, n
      if d[j, i] + d[i, k] < d[j, k]
        d[j, k] = d[j, i] + d[i, k]

你不能只对 for 循环重新排序而不改变条件，因为这样你会得到一个不同的算法——谁知道它做了什么。

于 2013-01-26T22:03:40.747 回答
2

在

for (k = 0; k < n; ++k)
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

最外面的循环k是指可能在Vi和之间的路径上的顶点Vj。因此k=1，例如，当您正在考虑顶点之间的所有路径Vi并且Vj包括顶点V1时

Vi .... V1 .... Vj

更重要的是，从这些路径中，您选择了最好的放松方式

if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

同样，每次迭代都集中在两个顶点上Vi，Vj并选择它们之间的最佳路径。

在另一个失败的例子中，您没有在两个固定顶点之间的路径中选择最佳路径Vi，Vj而是在整个地方放松，从不等待足够长的时间来找出两个集合顶点之间的路径是最好的。

在 Geekviewpoint，一个我非常依赖的网站，他们独特地使用x和v作为顶点和t最外层循环，这很容易记住它t是临时的，因此不是端点之一。（我希望他们实际上已经解释过了，因为这对每个人来说都不是显而易见的。）

//dynamically find the shortest distance between each pair.
    for (int t = 0; t < n; t++) {
      for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
          if (dist[v][u] > (long) dist[v][t] + dist[t][u]) {
            dist[v][u] = dist[v][t] + dist[t][u];
            pred[v][u] = pred[t][u];
          }
        }
      }
    }
于 2013-01-26T23:57:26.550 回答
0

我为第二个有缺陷的算法找到了一个反例。
当 i=0, j=1 时，它会尝试寻找中介，但没有。
然后，当 i=0、j=1 的中介可用时，不再检查它。 在此处输入图像描述

于 2013-01-26T22:22:50.380 回答
0

基本上，当您具有K价值时，loop k这意味着您将要添加另一条边，并且所有可能的方式都(i->j)使用 edge 进行更新(1->K-1)。然后你插入另一个边缘K，你再次检查是否有任何方法可以(i->j)使用这个边缘以更便宜的方式进行。所以你写d[i][j]=min(d[i][j],d[i][k]+d[k][j])。

所以如果你想写

  for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
     for(int k=0;k<n;k++)

您的更新应该是d[j][k] = min(d[j][k],d[j][i]+d[i][k])

于 2019-11-09T13:26:24.970 回答