ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)

【Java】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)  


 最小全域木(全ての頂点を最小コストで繋ぐ)、単一始点最短経路(始点から到達点までの最短距離)の他には全点対間最短経路(各頂点間の最小コスト[最短距離])を求めるアルゴリズムとしてワーシャル-フロイド法というものがある。

 解説などは Wikipedia他のホームページなどに譲るが、簡単な考え方としては、頂点(i → j)のコストと、中継点を含んだ(i → k → j)のコストを全パターン比較して、最小を求めることによって、各頂点同士の最短距離を記録していくと考えれば良い。紙に3つの頂点を書いて、(A → B と A → C → B)、(B → C と B → A → C)、(C → A と C → B → A)のようにぐるぐる基準点を回転して、小さいコストを記録していく感じだ。頂点が増えても、その三角路が組み合わさっている感じになる(実際には見えない頂点間も最短計算に使用している)。

 また、このアルゴリズムも負の閉路(辺の重みの総和が負になるような閉路)を検出できるという特徴がある。というのは、各頂点間のコストの表を初期化する際、配列の d[i][i] となるような位置を0にしておくと(つまり自分から自分までのコストは当然0なので)、負の閉路があった場合、負の値になることによって判断できるというものである(例えば、頂点(i → i)=0、k が負のコストのとき、(i → k → i)<0 になり、比較したとき負の値に更新される。k が正の場合は0以下になることはない)。

 今回は前回までの辺情報の構造体は使用しない。とりあえず例(図)はこちらと同じものを使わせてもらった。


例(頂点番号と辺の重みを表す)

●ワーシャル-フロイド法[全点対間最短経路] WarshallFloyd
public class WarshallFloyd {

public static void main(String[] args) throws Exception {
new WarshallFloyd();
}

public WarshallFloyd() {
//図をデータにしたもの
int n = 6; //頂点数
int[][] adj = new int[][]{
//接続元ノード, 接続先ノード, 重み
{0, 1, 1},
{0, 3, 2},
{0, 4, 3},
{1, 2, 4},
{1, 4, 1},
{2, 4, 1},
{2, 5, 3},
{3, 4, 2},
{4, 5, 3}
};

//辺の情報を無向グラフ用にする(有向グラフでも構わない)
int[][] edges = new int[adj.length * 2][3];
int len = adj.length;
for (int i = 0; i < len; i++) {
edges[i] = adj[i]; //そのままコピー(シャローコピー)
//無向グラフにしたいので、逆方向も接続する
edges[i + len][0] = adj[i][1];
edges[i + len][1] = adj[i][0];
edges[i + len][2] = adj[i][2];
}

int[][] ans = warshallFloyd(n, edges); //各頂点間の最短コスト(表)

//表を出力
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j > 0) {
System.out.print(" ");
}
if (ans[i][j] == INF) {
System.out.print("INF");
} else {
System.out.print(ans[i][j]);
}
}
System.out.println();
}

//負の閉路の判定
System.out.println("Negative Cycle = " + isNegativeCycle(ans));
}

static final int INF = Integer.MAX_VALUE; //INF 値((int)1e9, 1 << 30, Integer.MAX_VALUE / 2 などでも良い)

//ワーシャル-フロイド法[全点対間最短経路(All Pairs Shortest Path)]
int[][] warshallFloyd (int n, int[][] edges) {
//初期化
int[][] d = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = (i == j) ? 0 : INF; //i と j が同じ位置(d[i][i])は、負の閉路チェックに使う
}
}

//隣接行列のように、重みを入れる
for (int i = 0; i < edges.length; i++) {
d[edges[i][0]][edges[i][1]] = edges[i][2];
}

//ワーシャル-フロイド法(全点対間最短経路)
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (d[i][k] == INF) {
continue;
}
for (int j = 0; j < n; j++) {
if (d[k][j] == INF) {
continue;
}
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}

return d;
}

//負の閉路チェック
boolean isNegativeCycle(int[][] d) {
int n = d.length;
for (int i = 0; i < n; i++) {
if (d[i][i] < 0) {
return true; //負の閉路がある
}
}
return false;
}
}


 今回の戻値は各頂点間での最小コスト(距離)の表となる。負の閉路のチェックは別の関数(isNegativeCycle())にしているが、最短路計算の関数(warshallFloyd())に入れて、d の代わりに null を戻すようにしても良いだろう(負の閉路があった場合、値が使えないので)。

 辺の情報は今までのように構造体は使わず、int[][] のまま使っている(ただし、無向グラフ用に逆方向を追加している。有向グラフでも構わない)。最短路計算(warshallFloyd())内で結果となる表(d[][])を初期化しているが、この「初期化~隣接行列のように、重みを入れる」部分を別の関数に独立すれば、他の形式に対応することもできるだろう。

 最短距離の更新する際の計算は INF 値のままでやるとオーバーフローを起こすので、処理をスキップしている。コードが長く感じるなら「if (d[i][k] == INF) continue;」のように1行にするのも良いだろう。

 オーダーは O(V3)なので、重い感じもするが、単一始点最短経路を全パターンやることを考えれば、こちらの方が簡潔だろう。そう考えれば、一気にそれぞれの頂点同士の最短を知りたいときに使える。ネットワーク上の負荷の軽い箇所を探すとかね。結果の○で囲んである値を図と比較してみると、最短に更新されているのがわかる。また、直接繋がってない経路(例えば、1 → 3 のような)コストも計算されていることがわかるだろう。負の閉路を試したければ、この例は無向グラフになっているので、適当にどこかのコストを負にすれば、Negative Cycle = true となる。


(関連記事)
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)
【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)
【Java】素集合データ構造[互いに素な集合] (Union Find Tree, Disjoint Set Forest)


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/180-8d2ccb1a
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop