Algoogle

Algorithm for Programming Contest

Warshall-Floyd法

基本情報


計算量
用途 全点対最短路を求める

N := 頂点数

解説


Warshall-Floyd法では, グラフ中の任意の2頂点i, j間の最短距離を求める.
あるkに対して同じグラフ中の点0..kまでの中継点を使うとき(必ずしも全てを通るわけではない)の最短路が求まっているとする.
そのとき2頂点i, jとkについてdist[i][k+1]とdist[k+1][j]は共に最短になっている. よってk+1を経由するかどうかで中継点として頂点0..k+1を使うときのi, j間の最短距離を更新することができる.
dist[i][j] = min(dist[i][j], dist[i][k+1] + dist[k+1][j]);
よってkまでの頂点を中継点を使って最短路が求まっている時, k+1までの頂点を中継点とした最短路も上の更新によって求まる.
当然中継点をひとつも使わない時ははじめから最短になっている.
これらからkについて0からN−ま1で回して, その中で全ての組の最短を更新すれば全ての2点間の最短路が求まることが分かる.

以上によって全点対最短路がもとまる. またWarshall-Floyd法は3重ループを回すだけで実装できるので制約が許すなら単一始点最短路を求めたいときなどでも使われる(コーディングのスピードを上げるため).

コード


(warshall_floyd.cpp) download
1
2
3
4
for(int k = 0; k < N; k++)
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);

問題


Comments