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

表記ゆれ

フロイドのアルゴリズム

ワーシャルのアルゴリズム