ワーシャル–フロイド法
昔の道路地図帳の巻末には、すべての都市のペアの間の距離をまとめた表がありました。ワーシャル–フロイド法はそんな表を計算する方法で、これまでに書かれた中でも最も短いアルゴリズムの1つです。三重ループと1回の比較だけで、すべての最短距離が決まります。
考え方
ダイクストラ法とベルマン–フォード法は、1つのスタートからの最短距離を求めます。ワーシャル–フロイド法は、すべてのノードから他のすべてのノードへの最短距離を一度に求め、ノードごとに1行1列の表にまとめます。エッジから直接わかることから始め、途中の経由点として使えるノードを増やしながら、表全体を改善していきます。
ステップごとに
表を埋めます。各ノードから自分自身へは 0、隣り合うノードの間はエッジの長さ、それ以外は無限大です。次に、各ノード k と各ペア i, j について、i から k への距離と k から j への距離の和が i から j への距離より小さければ、小さいほうの数を書き込みます。アルゴリズムはこれだけです。コードでは三重ループになり、k がいちばん外側です。
例
4つのノードと、長さ 3 のエッジ A–B、長さ 1 の B–C、長さ 5 の A–C、長さ 2 の C–D を考えます。表はこれらと、A–D と B–D の無限大から始まります。A のラウンドでは何も変わりません。A を通る道はどれも長いからです。B のラウンドでは B 経由の A から C: 3 + 1 = 4 が見つかり、5 より短くなります。C のラウンドでは C 経由の A から D: 4 + 2 = 6 と、B から D: 1 + 2 = 3 が見つかり、どちらも初めて見つかった道です。D のラウンドでは何も変わりません。最終的な表は A–B 3、A–C 4、A–D 6、B–C 1、B–D 3、C–D 2 です。
ループの順序が大事な理由
経由点 k は外側のループでなければなりません。k のラウンドの後、どのマスも最初の k 個のノードだけを経由点にしたときの最短距離になっていて、次のラウンドはその上に積み上げます。新しい経由点を通る最良の経路は、そこまでの最良の経路とそこからの最良の経路をつないだもので、どちらもすでに正しいからです。k を内側のループにするとこの保証が崩れ、間違った距離が残ることがあります。ラウンド中に表をその場で書き換えても安全です。k 自身の行と列はそのラウンドで変わらないからです。
歴史と用途
Bernard Roy が 1959 年にこの方法を記述しました。1962 年には、Stephen Warshall が、あるノードから別のノードへ到達できるかだけを問う推移閉包のために、Robert Floyd が最短経路のために、それぞれ発表しました。距離表や経路表の計算、ネットワークの直径の算出、どのノードからどのノードへ行けるかの判定に使われ、対角線に負の値が出れば負の閉路を見つけられます。
試してみよう
アプリを開いて「ステップ」を押してください。片側にグラフ、もう片側に表があります。各ラウンドでは現在の経由点の行と列が強調され、各ステップでは1つのペアのより短い距離が書き込まれ、足し合わせた2つのマスが枠で囲まれます。そのラウンドで変わったマスには色が付きます。スタートとゴールを選ぶと、表が完成したときに2つの間の最短経路が見られます。
よくある質問
ワーシャル–フロイド法の時間計算量は?
ノードが n 個なら、エッジの数にかかわらず O(n³) で、表のメモリは O(n²) です。小さなグラフや密なグラフでは第一の選択肢で、単純なループがとても速く動きます。
ワーシャル–フロイド法と、各ノードからのダイクストラ法、どちらがよい?
密なグラフや、エッジが負になりうる場合は、ワーシャル–フロイド法のほうが単純で、速さもほぼ同じです。エッジが負でない大きな疎グラフでは、各ノードからダイクストラ法を実行するほうが速くなります。
ワーシャル–フロイド法は動的計画法?
はい。最初の k − 1 個のノードについての答えを使って、経由点が最初の k 個のノードにある経路の問題を解きます。表は1つだけで、進みながら上書きします。
推移閉包とは?
距離は無視して、どのノードからどのノードへ到達できるかを表したものです。ワーシャル版のアルゴリズムは、「min」と「+」の代わりに「or」と「and」を使ってこれを計算します。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ワーシャル–フロイド法を試す