【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)

2015/06/05 Fri [edit]

　前回のプリム法は最小全域木を求めるアルゴリズム（全ての頂点を最小コストで繋ぐ）だったが、少し似ている単一始点最短経路アルゴリズム（始点から到達点までの最短距離）にダイクストラ法がある。考え方は同じようなもので、プリム法は最小となる各辺のコストを記録するのに対し、ダイクストラ法は始点から各頂点までの距離を最短で記録していく方法だ。Wikipedia によると、元々プリム法を参考にしたようなので(?)、少し書き換えるだけで簡単に作れる。

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

●ダイクストラ法[単一始点最短経路] Dijkstra

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

public class Dijkstra {

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

    public Dijkstra() {
        //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

        //隣接リスト
        @SuppressWarnings("unchecked")
        List<Edge>[] edges = new List[n];
        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < adj.length; i++) {
            edges[adj[i][0]].add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
            edges[adj[i][1]].add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
        }

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

    static final int INF = 100100100;    //INF 値(十分に大きな値)

    //ダイクストラ法[単一始点最短経路(Single Source Shortest Path)]
    int dijkstra(int n, List<Edge>[] edges, int s, int g) {
        int[] distance = new int[n];        //始点からの最短距離

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

        Queue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(s, s, 0));     //始点を入れる

        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小距離(cost)の頂点を取り出す
            if (distance[e.target] < e.cost) {
                continue;
            }

            //隣接している頂点の最短距離を更新する
            for (Edge v : edges[e.target]) {
                if (distance[v.target] > distance[e.target] + v.cost) {  //(始点～)接続元＋接続先までの距離    
                    distance[v.target] = distance[e.target] + v.cost;    //現在記録されている距離より小さければ更新
                    q.add(new Edge(e.target, v.target, distance[v.target]));  //始点～接続先までの距離    
                }
            }
        }

        return distance[g];    //到達できなかったときは、INF となる
    }

    //辺情報の構造体
    class Edge implements Comparable<Edge> {
        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 値(十分に大きな値)になる。ダイクストラ法の性質上、辺のコストに負の値は使えない（大小関係が崩れる、無限ループするなど）。

　隣接リストは List<Edge>[] のように List の配列で作っている。List のリスト（List<List<Edge>>）でも良いが、頂点数が固定なら、この方が簡潔だろう。「@SuppressWarnings("unchecked")」は警告を消しているだけなので、無くても動く。

　優先度付きキュー(PriorityQueue)に追加される辺情報(Edge)は始点からの距離(cost)を持った構造体を突っ込んでいる。つまり取り出されるのは、始点から順次繋がってきた頂点のいずれかの最短距離となる。

　優先度付きキュー(PriorityQueue)の順番は辺情報の構造体（Edge）に Comparable インタフェースを噛ませて、コストを比較しているが、PriorityQueue のコンストラクタに Comparator を匿名クラスで定義しても良いだろう。そうすれば優先順位は色々変更できる。例えば優先順位に「推定値」を用いれば「A*(A-star, エースター)アルゴリズム」となる。

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

●ダイクストラ法で選択した辺を返す版

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

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

        int ans = dijkstra(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));
        }
    }

    static final int INF = 100100100;    //INF 値(十分に大きな値)

    //ダイクストラ法[単一始点最短経路(Single Source Shortest Path)]
    //選択した辺を返す
    int dijkstra(int n, List<Edge>[] edges, int s, int g, List<Edge> paths) {
        int[] distance = new int[n];        //始点からの最短距離
        int[] parent = new int[n];          //接続元ノード

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

        Queue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(s, s, 0));     //始点を入れる

        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小距離(cost)の頂点を取り出す
            if (distance[e.target] < e.cost) {
                continue;
            }

            //隣接している頂点の最短距離を更新する
            for (Edge v : edges[e.target]) {
                if (distance[v.target] > distance[e.target] + v.cost) {  //(始点～)接続元＋接続先までの距離
                    distance[v.target] = distance[e.target] + v.cost;    //現在記録されている距離より小さければ更新
                    q.add(new Edge(e.target, v.target, distance[v.target]));  //始点～接続先までの距離
                    parent[v.target] = e.target;	//接続元を記録
                }
            }
        }

        //選択した辺(逆から辿る[到達点→始点])
        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 となる
    }
    ・・・（略）・・・
}

20
source = 0, target = 2, cost = 9
source = 2, target = 5, cost = 11
source = 5, target = 4, cost = 20

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

　隣接行列を使ったり、優先度付きキュー(PriorityQueue)を使わない方法もあるが、辺が多いときはオーダーが O(V²) [V:頂点の数] になるので注意。PriorityQueue を使う場合は実装にもよるが、おおよそ O(E lon V) [E:辺の数, V:頂点の数] と考えておけば良いだろう。

　迷路で敵がプレイヤーを追跡するときなどにも良いかもね（ただし、大きな迷路などでは A＊(A-star, エースター)[ダイクストラ法に推定値を入れ、枝刈りをするアルゴリズム]などが使われる事が多い）。その場合、このサンプルでは最後まで探索を行っているが、最短距離を求めた時点で探索終了した方が効率的だろう。実装が簡単なので、色々改造して使うと良い。