java - Floyd-Warshall 算法逻辑 - 卡住

Question

我正在尝试使用此逻辑来了解 adjacency matrix 发生了什么，但我很困惑它说的是 a b c d 的间距......

谁能解释一下这是怎么回事？

谢谢(标记为 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 是 dynamic programming问题。

用二维版本编写它几乎是标准的(也更容易):

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 中可以找到对状态的更深入的解释。 .