ワーシャルフロイド法とは?

ワーシャルフロイド法は最短経路問題で使われるアルゴリズムの1つです。重みが負の辺があっても負閉路がない限り使えます。

下のようになっている場合、0 → 1 と直接移動する場合は 10 ですが、2を経由して 0 → 2 → 1 と移動すると 3 で移動することができます。では任意の頂点から別の任意の頂点へ移動する場合の最短経路はどうなっているでしょうか?

ワーシャルフロイド法のアルゴリズムは以下のとおり。

3つの頂点 (始点、経由点、終点) を選んで距離を計算する。
現在の (始点 → 終点) の最短距離より短ければ、これを (始点 → 終点) の最短距離とする。
これをすべての頂点で計算する。

繰り返すことで最短経路を求めます。

WarshallFloydクラスの定義

ワーシャルフロイド法で最短経路を求めるためのWarshallFloydクラスを定義します。

コンストラクタで頂点数を保存するとともに隣接行列を用意します。また最短経路を求めるために、最短経路で終点の 1 つ前に訪れた頂点を記録する二次元配列も用意します。この配列には頂点 i から頂点 j までの最短経路が (i → … → k → j) の場合、i 行目 j 列目に jの直前に訪れた k を記録されます。

ShowAdjacencyMatrixメソッドはデバッグ用です。二次元配列 _aMat と _pMat に格納されている値を表示します。

SetEdgeメソッドは入力された辺の情報を二次元配列に格納します。

メインの部分であるGetSolutionメソッドを示します。ここでは 3つの頂点(始点、経由点、終点) を選んで、(始点 → 経由点 → 終点) の最短距離が現在の(始点 → 終点) の最短距離より短ければ、その距離を新たに(始点 → 終点) の最短距離とします。

このとき一番外側のループが経由点のループになるようにします。こうすることで 頂点 x を経由する経路の最短距離を調べるとき、x 未満の頂点のみを経由する経路の最短距離は既に確定しているため、最短距離をうまく更新することができます。

GetShortestDistanceメソッドは引数で渡された始点から終点までの最短距離を返します。

GetShortestPathメソッドは引数で渡された始点から終点までの最短経路を返します。_pMatのstart行を調べれば各列へ移動するために直前にとおる地点の頂点番号が記録されているので、それを終点から始点までたどっていき、逆順にすれば始点から終点までの最短経路を取得することができます。

実際に最短経路を求めてみることにします。

実行結果は以下のとおり。

負閉路の検出

負閉路とは、枝の重みの総和が負となる閉路です。一般的に負閉路が存在するグラフでは最短経路問題を解くことはできません。なぜなら負閉路のなかを移動し続けることで何度でも最短距離を更新することができるからです。

たとえば以下の場合に 0 → 1 の最短距離を考えます。

0 → 2 で -20、2 → 0 で -17、0 → 2 で -37、2 → 0 で -34というように直ちに 0 から 1 に向かわないことで最短距離を無限に更新することができてしまうのです。

負閉路が存在するグラフでは最短経路問題を解くことはできないのですが、ワーシャルフロイド法は負閉路の存在を検出することができます。

以下のコードを実行します。

負閉路が存在する場合、隣接行列の対角成分(始点と終点が同じ経路の最短距離)のどれかが負となります(この場合はすべて負になっている)。始点と終点が同じ経路の最短距離を調べることで、与えられたグラフに負閉路が存在するかどうかがわかるのです。