Floyd-Warshall算法逻辑 - 坚持

Question

我正在尝试使用这个逻辑来理解邻接矩阵发生了什么,但是我认为它与关于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];

Answer 1

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] )

但也许它可以帮助你用三维版本来描绘它,所以你可以更明确地看到所有的状态:

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中可以找到对这些状态稍微深入的解释.

Answer 2

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

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

所以它看起来：

“我当前从i到 的最短路径j是长度L0，我当前从i到的最短路径k是长度L1，我当前从k到的最短路径j是长度L2。

如果我将当前最短路径组合i to k成k to j一条新路径会怎样？这条新路径i to k to j比我当前的最短路径短吗i to j？如果是这样，它会累积长度L1并L2计算新的最短路径的长度。”

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