フロイドワーシャル法について

Question

フロイドワーシャル法について

フロイドワーシャル法は基本的に以下のようなループで実装されています。
k: 経由する点 i: 始点 j: 終点 dp[i][j]は経路の距離を持った配列

    for(int k=0; k<n; k++) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
            }
        }
    }

この通りの実装で任意の2頂点の最短経路が求められることは理解できるのですが、
わからない部分としてループの順序についてです。

なぜ経由するkを一番外側のループとして実装をするのでしょうか？
こうすればうまくいくからというのは理解できるのですが、なぜかと聞かれたときにはっきり答えが出ません。

youtube等で調べても見ましたがデモが多く、なぜこのようなループを書くかについてが理解できません。
ご存知の方がいましたらご教授ください。

Answer 1

kをいちばん外側でループさせることで、一度のループで最短経路を計算できるようになります。

仮にiを外側としてループを回した場合、0番目でスタートするものの計算を終えてから1番目をスタートするもの、というように計算が移っていきます。0番目のループで0→5→3という進み方が最短となったとして、5番目を計算したら5→3にもっと短いルートが見つかったとなっても、すでに計算済みの0→3にフィードバックされることはありません。

これに対して、途中経由地点のkを外側でループすると、同じ0→3というルートは経由地ごとに再計算されることになります。たとえば、0→3での最短ルートが0→5→9→3だった場合、k=9ではすでに0→5→9と9→3には最短の値が入りますので、必ず最短の値を計算できます。

Answer 2

i,j,k の全組み合わせについて、より近い距離(i→j と i→j→k の短い方)を求めてるんですよね。
どっちみち"総当たり"なんだからループの順序はどうでもいいように思えます。

※ 配列dpの列indexが一番内側のloopなのは(C/C++での)配列メモリ・レイアウトからしてより高速であろうけど。

Comments

[maisumakun]

> どっちみち"総当たり"なんだからループの順序はどうでもいいように思えます。

前に計算した値を後から使いうるという性質上、そうは問屋がおろさないです。

[episteme]

あー...そか、これも動的計画法のひとつか。