c++ - floyd warshall が 1 つの距離行列のみを使用するのはなぜですか?

Question

floyd warshall アルゴリズムの疑似コードを読みましたが、 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if 距離を節約するために 1 つの dist 行列を使用するだけです。n 個の dist 行列が必要だと思います.n は頂点の数です. または、少なくとも 2 つの dist 行列が必要です. 1 つは頂点 k-1 内の現在の最短パスを格納し、もう 1 つは頂点 k 内の最短パスを格納し、最初のパスは k+1 内の最短パスを格納します。頂点内の距離に対する元の行列の k k-1?

この図は、D0、D1、D2....D(n) が必要であることを示しています

Answer 1

あなたはここで部分的に正しいです。

Floyd Warshall Algorithm (つまり、NxN 行列) の出力は、任意の 2 つの頂点間の実際の最短経路を再構築するのに役立ちません。

これらのパスは、各頂点ペア (x, y) に使用される最後の中間頂点を格納するように、親行列 P を保持する場合に回復できます。この値を k とします。

x から y への最短パスは、x から k への最短パスと k から y への最短パスを連結したものであり、行列 P を指定して再帰的に再構築できます。

ただし、ほとんどのすべてのペアのアプリケーションでは、結果の距離行列のみが必要であることに注意してください。これらのジョブは、フロイドのアルゴリズムが設計されたものです。