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 は動的計画法の問題です。

2次元バージョンで書くのはほぼ標準的です（そして簡単です）：

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) を調べてから、最初に fromに、次に fromからに行くことでより短いパスを持つことができるかどうかk、各 のすべての -iteration を調べます。i, jikkj

したがって、次のようになります。

「 から への現在の最短パスiのj長さL0、 から への現在の最短パスiのk長さ、 からへの現在の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 に答える