algorithm - Floyd-Warshall はどのように動的アルゴリズムですか?

Question

Floyd-Warshall アルゴリズムは動的であるため、常に最適なソリューションを提供する必要があります。したがって、私を混乱させているのは、アルゴリズムの各セグメントでのこれらの最適解の性質が何であるかです。特に、次の 3 つの質問を理解しようとしています。

誰でもこれらの懸念に光を当てることができますか?

score 1 · Accepted Answer

反復 0 : 反復の前に、取得された最適解には、ノードを通過せずに到達できるノードが含まれます。そのため、最初の反復の前には、ノードからノードまでの距離しかわかりません。ノードからノードまでの距離は 0 です。

反復 1 : 最初の反復の後、エッジによって直接接続された任意の 2 つのノード間の距離が得られます。

反復 i : 2 つのノード間の距離がエッジiteration i以下で区切られた後。i

score 1 · Accepted Answer

外側のループがを反復することを思い出してください。これは、からへの候補パスが通過する可能性kのある「中間」頂点です。ij

for k in 0..N-1
    for i in 0..N-1
        for j in 0..N-1
            g[i,j] = min(g[i,j], g[i,k]+g[k,j])

したがって、すべての反復の前に、部分解 (この時点では変更されていない隣接行列と同等) は、直接からiに向かうすべての最短経路jが表される最終解のサブセットを表します。

1 回の反復の後、最初の頂点 ( index ) を通過する最短パスが0ミックスに追加されます。

反復後K、部分解には、(1) 直接、または (2) のセットから 1 つまたは複数の頂点を通過する最短パスが含まれます{0..K-1}。もちろん、Kに到達したらN、ソリューションは完了です。

2 に答える 2