【わーしゃるふろいどほう】
ワーシャル・フロイド法 とは？
公開:
💡 経由地を1つずつ解禁して、距離表を更新する
すべての頂点の組み合わせの最短距離を求めるアルゴリズム。経由してよい頂点を順に増やし、距離表を更新する。負の辺も扱えるが、負の閉路には注意が必要。
📌 このページのポイント
ひよこ すべての場所から、すべての場所への近道を調べられるの？
ペンギン先生 それが全点対最短経路の問題だよ。ワーシャル・フロイド法は、出発点と到着点の組ごとに距離を入れた表を用意し、経由してよい頂点を少しずつ増やして更新するんだ。
ひよこ 経由地を増やすと、どう変わるの？
ペンギン先生 1→4の直接の距離が9でも、1→2が3、2→3が2、3→4が−2なら、その経路は3+2−2=3になる。直接行くより短いね。図はこの辺だけを持つ有向グラフの例だよ。
ひよこ 更新する式は難しいの？
ペンギン先生 頂点kを経由しない今の距離と、i→k→jの距離を比べて小さい方を残すよ。標準形ではkのループを一番外側にする。途中まで使ってよい経由地をそろえることが、この更新の意味を支えているんだ。
ひよこ マイナスの距離があっても大丈夫なの？
ペンギン先生 負の辺があるだけなら扱えるよ。ただし、回るほど合計が減る負の閉路を通って到着できる組では、有限の最短値がなくなる。すべての組が必ず影響されるわけではないけれど、単なる距離表として出す前に検出が必要だよ。
ひよこ 大きな地図でも使いやすいのかな？
ペンギン先生 頂点数Vに対して標準実装の更新回数はVの3乗に比例し、距離表は2乗に比例する。頂点が多いと重いので、疎なグラフや一部の出発点だけを調べる場合は別方式も比べよう。到達不能を表す大きな数の足し算でオーバーフローしない実装も大切だね。
まとめ：ざっくりこれだけ覚えればOK！
「ワーシャル・フロイド法」は「経由地を1つずつ解禁して、距離表を更新する」と押さえておこう！
📖 おまけ：英語の意味
「Floyd–Warshall algorithm」 ＝ FloydとWarshallの名を持つ最短経路アルゴリズム
💬 人名を含むアルゴリズム名で、日本語ではワーシャル・フロイド法とも呼ぶよ。