東大ニート

東大卒のニートが勉強したことをメモするブログ

<アルゴリズム>ワーシャルフロイド法

AOJの0200の問題(Traveling Alone: One-way Ticket of Youth | Aizu Online Judge)が最短経路問題だったのですが、ワーシャルフロイド法で解いてみたので、学んだ内容をメモしておきます。

こちらのサイトを参考にさせていただきました。

fantom1x.blog130.fc2.com

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

ワーシャル-フロイド法 - Wikipediaによると、「ワーシャル-フロイド法(英: Warshall-Floyd Algorithm)は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。」とのことです。
解説読んでもわからないところがあったので、以下に自分なりのイメージをメモしておきます。

使いどころ

AOJ0200のような(ある1つの組み合わせではなく)全点対間について、コストが最小(または最大)となる値を求める時に利用できます。

イメージとしては、

  • グラフがでてきた
  • 全ペアの最短コストを求めたい

となったら使えないか検討してみるといいのではないでしょうか。

アルゴリズムのポイント

基本的な考え方はグラフに含まれる頂点( i → j )のコストと、頂点kを経由した( i → k → j )のコストを全パターン比較し、最小となるものを記録していくというものです。

使い方のイメージとして、AOJ0200で私がJavaで書いたコードは以下のようになります。

  1. import java.util.Scanner;
  2. public class Main {

  3.    static Scanner sc = new Scanner(System.in);

  4.    static int n, m;

  5.    static int cost = new int[101][101];

  6.    static int time = new int[101][101];

  7.    public static void main(String args[]){

  8.       while(true) { 

  9.          n = sc.nextInt(); 

  10.          m = sc.nextInt();

  11.          if (n == 0 && m == 0) break;

  12.          //cost配列、time配列の初期化(INF値(2の29乗)を入力)

  13.          for (int i = 0; i < m + 1; i++) {

  14.             for (int j = 0; j < m + 1; j++) {

  15.                cost[i][j] = time[i][j] = 1<<29;

  16.             }

  17.          }

  18.          //隣接する頂点間のcostとtimeを登録
  19.          for (int i = 0; i < n; i++) {

  20.             int a = sc.nextInt();

  21.             int b = sc.nextInt();

  22.             cost[a][b] = cost[b][a] = sc.nextInt();

  23.             time[a][b] = time[b][a] = sc.nextInt();

  24.          }

  25.          warshallFloyd();

  26.          //出力処理
  27.          int k = sc.nextInt();

  28.          for (int i = 0; i < k; i++) {

  29.             int start = sc.nextInt();

  30.             int end = sc.nextInt();

  31.             int r = sc.nextInt();

  32.             if (r == 0) {

  33.                System.out.println(cost[start][end]);

  34.             } else {

  35.                System.out.println(time[start][end]);

  36.             }

  37.          }

  38.       }

  39.    }

  40.    static void warshallFloyd(){

  41.       for (int k = 0; k <= m; k++) { 

  42.          for (int i = 0; i <= m; i++) {

  43.             for (int j = 0; j <= m; j++) {

  44.                cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);

  45.                time[i][j] = Math.min(time[i][j], time[i][k] + time[k][j]);

  46.             }

  47.          }

  48.       }

  49.    }

  50. }

特にポイントとなるのは45行目〜54行目のwarshallFloydメソッドのところです。

頂点i, jに対して、頂点kを経由するルートを順々に調べていきますが、kのforループを一番外側に置くようにします。これだけで、すべてのループがまわると頂点( i , j )の最小コストはcost[i][j]に、最小時間はtime[i][j]に格納される、という非常にシンプルなアルゴリズムです。

また、3重のforループのため、頂点の数がnであれば、計算量はO(n^3) となります。nが200くらいまでであれば、TLEにならないのではないでしょうか。

しかし疑問もわく

やり方は非常にシンプルなのですが、これで本当に最小値が取れるのか、はじめは疑問でした。経由点kの検討する順番によって、最小値がうまく取れないのではないかと思ったのです。

例えば 以下のようなグラフが与えられ、経由点を1, 2, 3, 4の順に調べたとします。

f:id:todai_neet:20150911192033j:plain

この時、1→4の最小値については

  • 2が経由点となる時に1→4と1→2→4を比較
  • 3が経由点となる時に1→3→4も比較

となるので、すべての行き方が検討されているとわかります。

ただ、1→2の最小値については、1→2と1→4→2は検討されるけど、
1→3→4→2については正しく検討されないのではと思ったのです。

よく考えると、3が経由点となる時に1→3→4の行き方が検討され、4が検討される時に1→4→2が検討されるので、結果的に1→3→4→2も検討されるのですが、どの順番でも大丈夫かなと不安になりました。

ちょっと考えてみた

2点間の通り道は何通りもありますが、上記のアルゴリズムで、その全てが検討対象となっていれば問題なし、そうでなければ問題ありということになります。

例えば、点Pから点Qへの通り道として点A1〜点Anを経由するとします。

f:id:todai_neet:20150911200844j:plain

A1〜Anがどの順番に経由点として検討されたとしても、上記の通り道は検討対象となるのでしょうか。

Aiが経由点として検討されると、

f:id:todai_neet:20150911201704j:plain

 Ai-1→Ai→Ai+1の通り道が検討されます。

すると、その後でAi-1が経由点として検討された時に、Ai-1→Ai+1が検討されれば、Ai-1→Ai→Ai+1についても検討されたことになります。つまり、経由点として調べた点の前後を調べれば、先に調べた経由点を通る道も検討されるということです。

そのため、残りn-1個の経由点を検討すれば、どの順番に検討しても、上記の点Pから点Qへの通り道は検討されます。

こう考えると、どの順番で経由点を検討しても、すべての通り道が検討対象となることがわかります。

これで(私としては)納得してワーシャルフロイド法を使えますね(笑)

 

実装のポイント(Java)

ではここからワーシャルフロイド法を実装する上でのポイントをまとめていきます。

ポイント1. 各頂点間のコストを登録するための2次元配列を作り、初期化する(6・7・15〜19行目)

上記の例でいうcost配列とtime配列が該当します。頂点( i , j )の情報をcost[i][j]に登録するため、頂点数がm個の場合、配列の要素はm+1個ずつとします。
(頂点( i , j )の情報をcost[i-1][j-1]に登録する場合、要素はm個で大丈夫です

ポイント2. 隣接する頂点間のコストの登録(21〜26行目)

隣接する頂点間のコストを登録します。頂点( i , j )の情報はcost[i][j]だけでなくcost[j][i]にも登録するようにします。

ポイント3. 3重のforループによる最小値の取得(45〜54行目)

前述した通り、経由点のループを一番外側に起き、中に2つの頂点のループを置きます。ループの中では、既存のコストと経由点kを通る時のコストの2つを比較し、より小さいをコストを登録します。
「cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);」のように記述します。

 

以上で、ワーシャルフロイド法のメモを終わります。
最短経路の問題にはワーシャルフロイド法以外にもダイクストラ法など、様々な方法があるので順次調べていきたいです。