【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)

2015/06/06 Sat [edit]

　前回同様の単一始点最短経路アルゴリズムにベルマン-フォード法がある。よく見ればわかるが、ダイクストラ法の最短距離の更新処理をそのまま抜き出した感じだったりする。ダイクストラ法との違いは、計算順序が辺の総当り的な方法になっていることだろう。そのためオーダーが O(VE)[頂点数×辺の数]になっている。

　また、そのオーダー O(VE)[頂点数×辺の数]から、負の閉路（辺の重みの総和が負になるような閉路）があったとき、最短距離の更新が無限ループすることから、負の閉路を検出することもできる。

　今回も前回と比較するために、同じ例、同じ辺情報の構造体を使って試してみよう。

●ベルマン-フォード法[単一始点最短経路] BellmanFord

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BellmanFord {

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

    public BellmanFord() {
        //Wikipedia の例(図)をデータにしたもの
        int n = 6;    //頂点数
        int s = 0;    //スタート頂点(頂点番号は -1 されている[元は 1])
        int g = 4;    //ゴール頂点(頂点番号は -1 されている[元は 5])
        int[][] adj = new int[][]{
            //接続元ノード, 接続先ノード, 重み
            {0, 1, 7},
            {0, 2, 9},
            {0, 5, 14},
            {1, 2, 10},
            {1, 3, 15},
            {2, 3, 11},
            {2, 5, 2},
            {3, 4, 6},
            {4, 5, 9}
        };    //s:0 → g:4 のとき、答えは 20

        //辺情報の配列を作る
        List<Edge> list = new ArrayList<Edge>();
        for (int i = 0; i < adj.length; i++) {
            list.add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
            list.add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
        }

        Edge[] edges = list.toArray(new Edge[0]);    //配列に変換

        int ans = bellmanford(n, edges, s, g);
        System.out.println(ans);    //s → g の最短距離
    }

    //ベルマン-フォード法[単一始点最短経路(Single Source Shortest Path)]
    int bellmanford(int n, Edge[] edges, int s, int g) {
        int[] distance = new int[n];        //始点からの最短距離
        int[] count = new int[n];           //更新カウント(負の閉路チェック用)

        Arrays.fill(distance, Integer.MAX_VALUE);    //各頂点までの距離を初期化(INF 値)
        distance[s] = 0;    //始点の距離は０

        boolean negative = false;     //負の閉路フラグ
        boolean update = true;        //更新フラグ

        while (update && !negative) {
            update = false;
            for (Edge e : edges) {
                //接続元＋接続先までの距離
                if (distance[e.source] != Integer.MAX_VALUE && distance[e.source] + e.cost < distance[e.target]) {
                    distance[e.target] = distance[e.source] + e.cost;    //現在記録されている距離より小さければ更新
                    update = true;

                    if (++count[e.target] >= n) {    //負の閉路チェック
                        negative = true;
                        break;
                    }
                }
            }
        }

        if (negative) {
            return Integer.MIN_VALUE;    //負の閉路があったときは、-INF(Integer.MIN_VALUE)を返す
        }
        return distance[g];    //到達できなかったときは、INF(Integer.MAX_VALUE)になる
    }

    //辺情報の構造体
    class Edge implements Comparable {
        public int source = 0;    //接続元ノード
        public int target = 0;    //接続先ノード
        public int cost = 0;      //重み

        public Edge(int source, int target, int cost) {
            this.source = source;
            this.target = target;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }

        @Override
        public String toString() {    //デバッグ用
            return "source = " + source + ", target = " + target + ", cost = " + cost;
        }
    }
}

　ゴールの頂点に到達できなかったときは、戻値が INF 値(Integer.MAX_VALUE)になる。また、負の閉路があったときは、-INF 値(Integer.MIN_VALUE)を返している。わかりにくければ、適当に -1 などに変更しても良いだろう。

　ベルマン-フォード法は辺の総当りなので、隣接リストではなく、より簡潔に、線形的な配列（Edge[]）にしている。

　負の閉路の検出には各頂点の更新数（count[]）で判別している。これは負の閉路がなければ、各頂点の更新は n - 1 を超えることはないからだ（例えば頂点が全部で５コなら、１つの頂点には辺は４つまでしか繋がらない＝更新も４回まで）。オーダー O(VE)[頂点数×辺の数]から、全体のループ「while (update && !negative) {}」を、Wikipedia のコードのように頂点数の回数「for i from 1 to size(vertices) - 1:」のようにするならば、更新数は配列ではなく、int 型などにして「count >= n * edges.length」にしても良いだろう。ただし、計算量は増える。

　最短距離の更新の条件に「if (distance[e.source] != Integer.MAX_VALUE && ～」という条件が含まれるが、これは Integer.MAX_VALUE に加算をすると、オーバーフローを起こし、マイナスの値になってしまうためだ。これはダイクストラ法と違って、順次始点から近い頂点から計算されるわけでなく、辺情報の配列を無秩序に計算するためなので、初期化のデフォルト値を、コストを加算しても十分大きな値（(int)1e9, 1 << 30, Integer.MAX_VALUE / 2 など）にすれば、この条件文を消すことができる。

　この例では戻値は単一始点最短経路のコストを返しているが、選択した辺を知りたければ、少し改造して、各頂点の最短距離を更新するときに、その接続元を記録しておき、逆から辿れば(到達点→始点)わかる。頂点番号だけでも良いが、今回も前回に合わせて、辺情報の構造体で返すようにしてみよう。

●ベルマン-フォード法で選択した辺を返す版

・・・（略）・・・
import java.util.Collections;
import java.util.LinkedList;

public class BellmanFord {
    ・・・（略）・・・
    public BellmanFord() {
        ・・・（略）・・・
        List<Edge> paths = new LinkedList<Edge>();    //選択した辺(戻値用)

        int ans = bellmanford(n, edges, s, g, paths);
        System.out.println(ans);    //s → g の最短距離

        //選択した辺(確認)
        int len = paths.size();
        for (int i = 1; i < len; i++) {    //一番最初[0]は始点のためスキップ
            System.out.println(paths.get(i));
        }
    }

    //ベルマン-フォード法[単一始点最短経路(Single Source Shortest Path)]
    //選択した辺を返す。
    int bellmanford(int n, Edge[] edges, int s, int g, List<Edge> paths) {
        int[] distance = new int[n];        //始点からの最短距離
        int[] parent = new int[n];          //接続元ノード
        int[] count = new int[n];           //更新カウント(負の閉路チェック用)

        Arrays.fill(distance, Integer.MAX_VALUE);    //各頂点までの距離を初期化(INF 値)
        Arrays.fill(parent, -1);    //-1 は始点または未到達
        distance[s] = 0;    //始点の距離は０

        boolean negative = false;     //負の閉路フラグ
        boolean update = true;        //更新フラグ

        while (update && !negative) {
            update = false;
            for (Edge e : edges) {
                //接続元＋接続先までの距離
                if (distance[e.source] != Integer.MAX_VALUE && distance[e.source] + e.cost < distance[e.target]) {
                    distance[e.target] = distance[e.source] + e.cost;    //現在記録されている距離より小さければ更新
                    parent[e.target] = e.source;    //接続元を記録
                    update = true;

                    if (++count[e.target] >= n) {    //負の閉路チェック
                        negative = true;
                        break;
                    }
                }
            }
        }

        if (negative) {
            return Integer.MIN_VALUE;    //負の閉路があったときは、-INF(Integer.MIN_VALUE)を返す
        }

        //選択した辺(逆から辿る[到達点→始点])
        paths.clear();
        if (parent[g] > -1) {
            int p = g;
            while (p > -1) {
                paths.add(new Edge(parent[p], p, distance[p]));
                p = parent[p];
            }
            Collections.reverse(paths);    //反転する(始点→到達点)
        }

        return distance[g];    //到達できなかったときは、INF(Integer.MAX_VALUE)になる
    }
    ・・・（略）・・・
}

　頂点だけで良ければ、選択した辺を作っている所を、List<Integer> などにして、p だけを追加していけば良い（引数部分も型に合わせる）。[0] は始点になるので、List.remove(0) で除去しても良い。

　ベルマン-フォード法は負の閉路を持っている可能性がある場合や、迷路というより、網の目のようなネットワーク経路などに向いているかも知れない。このサンプルでは更新がなかったとき、探索を打ち切っているので、計算量は「辺の数×頂点数」よりもずっと小さい回数で済む。デバッグ出力して確かめてみると、負の閉路がない場合は「辺の数＋数回の更新」で終わることが多いので（データの順序にもよる。始点に近い順に並んでいると計算が速い）、ダイクストラ法とそれほど変わらない気がする。