- 現在の経由点
- 経由点済み
- 短くなったペア
- 経路
ワーシャル–フロイド法
どの町からどの町へも、距離はどれだけ? ワーシャル–フロイド法は、表と三重ループでそれを一度に答えます。ラウンドごとに途中の経由点として使えるノードが1つ増え、すべてのペアについて、そこを回り道したほうが短いかを調べます。ステップごとに進めて、表が埋まり距離が下がっていく様子を見てみましょう。 「再生」で表が埋まっていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。表には、すべてのノードのペアについて、その時点で見つかっている最短距離が入ります。各エッジの数字はその長さです。ラウンドごとに途中の経由点として使えるノードが1つ増え、各ステップでは、そのノードを経由して短くなるペアを示します。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、最後に2つの間の最短経路が見られます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
- 表に注目しましょう。現在の経由点の行と列に色が付き、各ステップでより短い距離が書き込まれます。
- スタートとゴールを選ぶと、最後に2つの間の最短経路が見られます。「新しいグラフ」で別のグラフを試せます。
ワーシャル–フロイド法のしくみ
ノードごとに1行1列の表を作ります。対角線には 0、2つのノードがエッジでつながっているところにはその長さ、それ以外には無限大を入れます。次に、各ノード k を順に経由点の候補にします。各ペア i, j について、表の i から j への距離と、i から k への距離に k から j への距離を足したものを比べ、小さいほうを残します。最後のノードの後には、どのマスも2つのノード間の最短距離になっています。
なぜうまくいくのか
k のラウンドの後、表にはすべてのペアについて、経由点がすべてそれまでに処理したノードである最短経路が入っています。次のノードのラウンドでは、そのノードが役に立つかだけを判断すれば済みます。そのノードを通る最短経路は、そこまでの最短経路とそこからの最短経路をつないだもので、どちらもすでに表にあります。このように、すでに求めた小さな答えから大きな答えを組み立てる方法を動的計画法と呼びます。負のエッジがあってもうまくいき、対角線に負の数が現れれば負の閉路があるとわかります。
よくある質問
ワーシャル–フロイド法とは?
重み付きグラフで、すべてのノードのペアの最短距離を求めるアルゴリズムです。距離の表を持ち、各ノードについて順に、そのノードを通るとどこかのペアが短くなるかを調べます。
ワーシャル–フロイド法はどれくらい速い?
n 個のノードについて三重ループがあるので、計算量は n³ で増え、表には n² 個のマスが必要です。数百ノードのグラフなら問題ありません。大きな疎グラフでは、各ノードからダイクストラ法を実行するほうが速くなります。
ワーシャル–フロイド法は負のエッジを扱える?
はい、負の閉路がなければ扱えます。負の閉路があると、対角線のどこかのマスが負になります。ワーシャル–フロイド法はこれで負の閉路を検出します。
距離だけでなく経路を得るには?
i から j への途中の次のノードを記録する、もう1つの表を持ちます。あるペアが k 経由で短くなるたびに、i から k へ向かう次のノードを写します。その表を i から j までたどると経路がわかります。
グラフはどこかに送信されますか?
いいえ。グラフの作成と表の計算はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ