2

Floyd-Warshall アルゴリズムを理解するのに苦労しています。手で行う方法を知っているのと同じように、それがどのように機能するかは知っていますが、コンピューターの知覚を通じて理解する必要があります。

FOR k <-- 1 TO N DO
    FOR i <-- 1 TO N DO
        FOR j <-- TO N DO 
            IF Djk + Dkj < DiJ THEN
                Dij <-- djk + dkj

k、iおよびjは反復用の変数であり、値まで反復しnます。これはネストされたループであり、各ノードを調べてから最短パスを見つけますか?

4

2 に答える 2

4

Floyd-Warshall における k の大幅に単純化された意味は、グラフの「中間点」です。最後の 2 行は、次のように解釈できます。「i から k へ、次に k から j へ、これまでに見つけたどのパスを介しても i から j へのパスよりも速く到達できる場合、i から k を介して j へのパスは次のようになります。新しい最短経路」。

于 2011-11-23T18:39:49.353 に答える
1

K は中間頂点を表します。したがって、外側のループは基本的に、K 番目の頂点を中間停止点にすると言っています。内側の 2 つのループは、隣接行列の各項目をチェックし、K を使用した距離 (K を中間頂点として使用) が、頂点 i から j までの距離 (隣接の位置 i、j の数) より小さいかどうかをチェックします。マトリックス）。距離が小さい場合は、d[i,j] を更新します。

于 2014-06-01T22:08:18.963 に答える