フロイド・ワーシャル法（Floyd–Warshall）とは？全ペア最短経路を求めるアルゴリズムを解説

フロイド・ワーシャル法（Floyd–Warshall algorithm）は、重み付きグラフに対する「全ペア最短経路問題」を解くための代表的なアルゴリズムです。グラフ上のすべての頂点の組み合わせについて最短距離を一括で求め、その結果を「任意のノードから他のすべてのノードへの最小距離」を表す行列（距離行列）として出力します。

アルゴリズムの基本的な考え方

処理の流れは非常にシンプルです。

• 初期化： 出力用の行列を、グラフのコスト行列（隣接行列）と同じものにします。直接つながっていない頂点間の距離は ∞（無限大）として扱います。
• 更新： 各頂点 k を「中継地点」として仮定し、「i → k → j と経由するほうが i → j の現在の距離より短いか」をすべての頂点の組 (i, j) について調べます。より短ければ cost[i][j] を更新します。
• 反復： この操作をすべての頂点 k について繰り返すことで、あらゆる中継パターンが反映された最短距離行列が完成します。

計算量は O(V³)（V はグラフの頂点数）です。三重ループという単純な構造でありながら、ダイクストラ法と異なり負の重みを持つ辺が含まれていても（負の閉路が存在しない限り）正しく動作する点が大きな特徴です。

入力と出力

入力：グラフのコスト行列
0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

出力：全ペア最短経路の距離行列
0 3 5 4 6 7 7
3 0 2 1 3 4 4
5 2 0 1 3 2 3
4 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0

アルゴリズム（擬似コード）

floydWarshall(cost)
入力 − グラフのコスト行列 cost
出力 − 任意の頂点間の最短距離を格納した行列

Begin
    for k := 0 to n-1, do
        for i := 0 to n-1, do
            for j := 0 to n-1, do
                if cost[i,k] + cost[k,j] < cost[i,j], then
                    cost[i,j] := cost[i,k] + cost[k,j]
            done
        done
    done
    現在のコスト行列を表示する
End

C++による実装例

#include <iostream>
#include <iomanip>
#define NODE 7
#define INF 999
using namespace std;

// グラフのコスト行列
int costMat[NODE][NODE] = {
    {0, 3, 6, INF, INF, INF, INF},
    {3, 0, 2, 1, INF, INF, INF},
    {6, 2, 0, 1, 4, 2, INF},
    {INF, 1, 1, 0, 2, INF, 4},
    {INF, INF, 4, 2, 0, 2, 1},
    {INF, INF, 2, INF, 2, 0, 1},
    {INF, INF, INF, 4, 1, 1, 0}
};

void floydWarshall() {
    int cost[NODE][NODE];   // 全ノード間の最短距離を格納する行列
    for(int i = 0; i<NODE; i++)
        for(int j = 0; j<NODE; j++)
            cost[i][j] = costMat[i][j];   // コスト行列を新しい行列にコピー

    // 頂点 k を中間頂点として最短距離を更新
    for(int k = 0; k<NODE; k++) {
        for(int i = 0; i<NODE; i++)
            for(int j = 0; j<NODE; j++)
                if(cost[i][k]+cost[k][j] < cost[i][j])
                    cost[i][j] = cost[i][k]+cost[k][j];
    }

    cout << "The matrix:" << endl;
    for(int i = 0; i<NODE; i++) {
        for(int j = 0; j<NODE; j++)
            cout << setw(3) << cost[i][j];
        cout << endl;
    }
}

int main() {
    floydWarshall();
}

この実装では、直接つながっていない頂点間の距離を表すために INF = 999 を「無限大」として使用しています。まず元のコスト行列を作業用の行列にコピーし、その後、三重ループによって各頂点を中間頂点とした経路の改善を繰り返します。

実行結果

The matrix:
  0  3  5  4  6  7  7
  3  0  2  1  3  4  4
  5  2  0  1  3  2  3
  4  1  1  0  2  3  3
  6  3  3  2  0  2  1
  7  4  2  3  2  0  1
  7  4  3  3  1  1  0

このように、フロイド・ワーシャル法を使えば、頂点数 V のグラフに対して O(V³) の計算量で全頂点対間の最短距離を一度に求めることができます。実際の経路（どの頂点を通るか）まで復元したい場合は、更新時に中間頂点 k を記録するもう一つの行列を用意しておくとよいでしょう。