Floyd–Warshall Algorithm
あるグラフについて、すべての頂点対間における最短経路を求めるアルゴリズム
Dijkstra法が対象にする問題は始点が1つだけ
表記の導入
$ d^k(i,j)
グラフの頂点$ vについて、$ k番目以下の頂点のみを経由できるという条件のもとでの$ v_iから$ v_jまでの最短経路の長さのこと
※$ k,i,jは自然数
Floyd's algorithm
$ d^{k-1}(i,j)が求まっているとき、$ d^k(i,j)について考える
$ d^k (i,j)が$ v_kを経由する場合
$ d^k (i,j) = d^{k-1}(i,j)
$ d^k (i,j)が$ v_kを経由しない場合
$ d^k (i,j) = d^{k-1}(i,k) + d^{k-1}(k,j)
以上を踏まえると $ d^{k}(i,j) = min \lbrace d^{k-1}(i,j), d^{k-1}(i,k) + d^{k-1}(k,j) \rbrace
$ k=0のとき
$ d^k(i,j) = d^0(i,j)は頂点対$ (i,j)を直接つなぐエッジの長さ(重み)に等しい
$ k=n(ただし$ n\ne 0)のとき
$ d^k(i,j) = d^n(i,j) = min \lbrace d^{n-1}(i,j), d^{n-1} (i,n) + d^{n-1}(n,j) \rbrace
つまり
定義
非零の自然数$ kについて
$ d^0(i,j) = w(i,j)
$ d^{k}(i,j) = min \lbrace d^{k-1}(i,j), d^{k-1}(i,k) + d^{k-1}(k,j) \rbrace
表記ゆれ
フロイドのアルゴリズム
ワーシャルのアルゴリズム
Floyd's algorithm
Warshall's Algorithm
フロイド-ワーシャル法
ワーシャル-フロイド法