ワーシャル・フロイド法

Jan 30, 2020

経路探索アルゴリズムの一つ「ワーシャル・フロイド法」についてを調べてみた。

ワーシャル・フロイド法とは？ #

ワーシャル・フロイド法とは、グラフのある頂点からある頂点までの最短経路を全ての組み合わせにおいて探索するアルゴリズムである。

入力
グラフ G = (V,E)
Eの各辺の重み(コスト)
出力
全ての頂点i,j(∈V)における最短経路

アルゴリズム #

アルゴリズムは以下の通り。

V = (頂点の数)
d[V][V]     // d[i][j]は頂点iから頂点jまでにかかるコスト。経路が存在しない場合はINF、i==jの時は0で初期化する
d ← E       // dに辺Eの長さを反映させる (d[i][j]にEの長さを入れる)

for(a = 0;a = V;a++){
    for(b = 0;b < V;b++){
        for(c = 0;c < V;c++){
            d[b][c] = min(d[b][c], d[b][a] + d[a][c])
        }
    }
}

return d

考え方としては、頂点iからグラフGの頂点それぞれを経由して頂点jまで行く計|V|通りの経路を調べ、調べた|V|通りのパターンの中から最小のコストを取り出したものが、頂点iから頂点jへの最小コストとなる。
これを全ての(i,j)の組み合わせにおいて調べることで、グラフGの全ての頂点間の最小コストを調べられる。全体の計算量はO(|V|³)となる。