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

2015/06/07 Sun [edit]

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

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

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

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

例（頂点番号と辺の重みを表す）

●ワーシャル-フロイド法[全点対間最短経路] 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;」のように１行にするのも良いだろう。

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