6

我试图用这个逻辑来理解邻接矩阵发生了什么，但我很困惑它所说的关于 abcd 的间隔......

谁能解释这里发生了什么？

谢谢（标记为 java 作为它向我们展示的语言，所以如果有人发布任何代码示例，他们可以看到它是用该语言编写的）

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

这是代码：

for (k = 0; k < n; ++k) {
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            /* If i and j are different nodes and if
               the paths between i and k and between
               k and j exist, do */
            if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                /* See if you can't get a shorter path
                   between i and j by interspacing
                   k somewhere along the current
                   path */
                if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
                        (dist[i][j] == 0))
                    dist[i][j] = dist[i][k] + dist[k][j];
4

2 回答 2

7

Floyd-Warshall 是一个动态规划问题。

在二维版本中编写它几乎是标准的（并且更容易）：

for ( int k = 0; k < n; k++ )
   for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
          dist[i][j] = min( dist[i][k] + dist[k][j], dist[i][j] )

但也许它可以帮助您使用 3 维版本来描绘它，因此您可以更清楚地看到所有状态：

for ( int k = 0; k < n; k++ )
   for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
          dist[k][i][j] = min( dist[k-1][i][k] + dist[k-1][k][j], dist[k-1][i][j] )

在Algorithmist中可以找到对状态的更深入的解释。

于 2010-04-22T12:16:39.453 回答
4

Floyd-Warshall 算法执行以下操作：

它查看每个节点 ( k)，然后查看每个节点的每次k迭代i, j，如果它可以通过先从itok再从kto获得更短的路径j。

所以看起来：

“我目前从ito 到的最短路径j是有长度的L0，我目前从ito 到的最短路径k是有长度的，我目前从to 到的L1最短路径是有长度的。kjL2

如果我将当前最短的路径i to k与k to j新路径结合起来会怎样？这条新路径是否i to k to j比我目前最短的路径短i to j？如果是这样，它会累积长度L1并L2计算新最短路径的长度。”

这意味着，是从到k的方式的潜在中途停留点。ij

于 2010-04-22T09:07:50.173 回答