全点対最短経路問題とは？ワーシャル・フロイド法の仕組みとC++実装例

ワーシャル・フロイド法（全点対最短経路）とは

全点対最短経路（All-Pair Shortest Path）問題を解くための代表的なアルゴリズムとして知られているのが「ワーシャル・フロイド（Floyd-Warshall）法」です。このアルゴリズムは、重み付きグラフが与えられた際に、すべての頂点ペア間の最短経路を一括して求めることができます。

アルゴリズムを実行すると、最終的に1つの行列が出力されます。この行列には、グラフ内の任意のノードから他のすべてのノードへの最小距離が記録されます。

処理の流れは次のとおりです。まず、出力用の行列をグラフのコスト行列（隣接行列）と同じ値で初期化します。その後、すべての頂点 k を順に「中間頂点」として候補に挙げながら、「i から k を経由して j に向かう経路」が現在の i→j の距離より短ければ、行列の値を更新していきます。この操作を全頂点に対して繰り返すことで、最終的な最短距離行列が完成します。

このアルゴリズムの計算量は O(V³) です。ここで V はグラフの頂点数を表します。また、負の重みを持つ辺も扱える一方、負閉路（負のコストで一周できる閉路）が存在する場合は正しい結果が得られないという特徴があります。

入力：グラフのコスト行列

以下は、7つの頂点を持つグラフのコスト行列の例です。「∞」は該当する頂点間に直接つながる辺が存在しないことを意味します。

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 4 5 6 7 7
3 0 2 1 3 4 4
4 2 0 1 3 2 3
5 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

アルゴリズムの手順

floydWarshal(cost)

入力： グラフのコスト行列

出力： 任意の頂点間の最短距離を格納した行列

Begin
    for k := 0 to n, do
       for i := 0 to n, do
          for j := 0 to n, do
             if cost[i,k] + cost[k,j] < cost[i,j], then
                cost[i,j] := cost[i,k] + cost[k,j]
             done
          done
       done
       display the current cost matrix
End

C++による実装例

続いて、上記のアルゴリズムをC++で実装した例を示します。元のコスト行列をコピーした作業用行列を用意し、三重ループによって中間頂点 k を順番に適用しながら距離を更新します。

#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 floydWarshal(){
    int cost[NODE][NODE]; // 全ノード間の最短距離を保存するための行列
    for(int i = 0; i<NODE; i++)
       for(int j = 0; j<NODE; j++)
          cost[i][j] = costMat[i][j]; // コスト行列を作業用行列へコピー
          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(){
    floydWarshal();
}

実行結果

プログラムを実行すると、すべての頂点ペア間の最短距離が格納された行列が出力されます。初期状態では到達できなかった頂点間の距離も、中間頂点を経由する経路が見つかることで更新されていることが分かります。

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

まとめ

ワーシャル・フロイド法は、動的計画法の考え方に基づいたシンプルな三重ループで実装でき、全頂点ペア間の最短経路をまとめて求められる強力な手法です。計算量は O(V³) と頂点数に対して増加するため、大規模グラフには不向きですが、頂点数が数百程度までの密なグラフや、すべてのノード間距離が必要な場面（交通網の分析、ネットワークルーティングなど）で特に有用です。