グラフのすべての2頂点間の最短路をワーシャルフロイド法で求める

programming contest C++

このエントリーをはてなブックマークに追加

ワーシャルフロイド法というのを使うと、グラフのすべての2頂点間の最短路を求められるらしい。蟻本を参考にして解いてみた。

以下のグラフを例にとって、全点対の最短路を求める。

コードは以下。

#include <cstdio>
#include <algorithm>

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

const int MAX_V = 200;
int d[MAX_V][MAX_V];

void setCost(int d[MAX_V][MAX_V], int s, int e, int cost){
    d[s][e] = d[e][s] = cost;
}


int main(){
    // 頂点の数
    const int V = 9;

    // 十分大きい数をとる
    const int INF = 1e4;

    // 辺のコストを初期化
    // i = jのときは0とする
    // 辺が存在しないときはINFとする
    REP(i, V){
        REP(j, V){
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }

    // 辺のコストを設定
    // (d, 0, 1, 2)は頂点0と頂点1の間のコストを2と設定するという意味
    setCost(d, 0, 1, 2);
    setCost(d, 0, 2, 5);
    setCost(d, 1, 3, 3);
    setCost(d, 1, 4, 1);
    setCost(d, 2, 4, 4);
    setCost(d, 2, 6, 1);
    setCost(d, 3, 4, 2);
    setCost(d, 3, 5, 8);
    setCost(d, 4, 5, 9);
    setCost(d, 4, 6, 2);
    setCost(d, 7, 8, 5);

    // Warshall Floyd
    REP(k, V){
        REP(i, V){
            REP(j, V){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    // 結果の表示
    REP(i, V){
        REP(j, V){
            printf("%5d ", d[i][j]);
        }
        printf("\n");
    }

    return 0;
}

結果は以下。各頂点間の最短距離を行列で表示している。頂点7と8とは離れ小島になっているので、その他の頂点との最短距離はINFとなっていることが分かる。

    0     2     5     5     3    12     5 10000 10000
    2     0     4     3     1    10     3 10000 10000
    5     4     0     5     3    12     1 10000 10000
    5     3     5     0     2     8     4 10000 10000
    3     1     3     2     0     9     2 10000 10000
   12    10    12     8     9     0    11 10000 10000
    5     3     1     4     2    11     0 10000 10000
10000 10000 10000 10000 10000 10000 10000     0     5
10000 10000 10000 10000 10000 10000 10000     5     0

参考