IK.AM

ダイクストラ法によるグラフ構造の最短経路を解くメモ。

隣接リストを使ったバージョンと隣接行列を使ったバージョン

以下の例題とてグラフを使う

隣接リスト

本当は↑のグラフは無向なんだけど、経路を定義するのが面倒だったので有向で。

PriorityQueueを使うと楽です

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

public class DijkstraList {

    /** 駅クラス */
    static class Station implements Comparable<Station> {
        String name;
        List<Route> routes = new ArrayList<Route>();
        /** 始点からのコスト */
        int cost = Integer.MAX_VALUE;

        public Station(String name) {
            this.name = name;
        }

        public void addRoute(Station to, int dist) {
            routes.add(new Route(this, to, dist));
        }

        @Override
        public String toString() {
            return name;
        }

        public int compareTo(Station o) {
            return cost - o.cost;
        }
    }

    /** 経路クラス */
    static class Route {
        Station from;
        Station to;
        /** 経路間コスト */
        int cost;

        public Route(Station from, Station to, int dist) {
            this.from = from;
            this.to = to;
            this.cost = dist;
        }
    }

    public static void main(String[] args) {
        Station[] stations = { new Station("横浜"), new Station("武蔵小杉"),
                new Station("品川"), new Station("渋谷"), new Station("新橋"),
                new Station("溜池山王"), };

        stations[0].addRoute(stations[1], 12);
        stations[0].addRoute(stations[2], 28);
        stations[1].addRoute(stations[2], 10);
        stations[1].addRoute(stations[3], 13);
        stations[2].addRoute(stations[3], 11);
        stations[2].addRoute(stations[4], 7);
        stations[3].addRoute(stations[5], 9);
        stations[4].addRoute(stations[5], 4);

        // 始点
        stations[0].cost = 0;

        // PQに挿入
        PriorityQueue<Station> pq = new PriorityQueue<Station>(
                Arrays.asList(stations));
        while (!pq.isEmpty()) {
            Station s = pq.poll();
            for (Route route : s.routes) {
                Station to = route.to;
                int cost = s.cost + route.cost;
                if (cost < to.cost) {
                    pq.remove(to);
                    // コストを更新して入れ替え
                    to.cost = cost;
                    pq.add(to);
                }
            }
        }

        for (Station s : stations) {
            System.out.println(stations[0] + " → " + s + " " + s.cost + "分");
        }
    }

}

実行結果

横浜 → 横浜 0分
横浜 → 武蔵小杉 12分
横浜 → 品川 22分
横浜 → 渋谷 25分
横浜 → 新橋 29分
横浜 → 溜池山王 33分

隣接行列

こっちは無向でやってみる

import java.util.Arrays;

public class DijkstraMatrix {

    public static void main(String[] args) {
        String[] stations = { "横浜", "武蔵小杉", "品川", "渋谷", "新橋", "溜池山王" };
        int n = stations.length;
        // 隣接行列
        int[][] adjacency_matrix = { { 0, 12, 28, 0, 0, 0 },
                { 12, 0, 10, 13, 0, 0 }, { 28, 10, 0, 11, 7, 0 },
                { 0, 13, 11, 0, 0, 9 }, { 0, 0, 7, 0, 0, 4 },
                { 0, 0, 0, 9, 4, 0 } };
        // 始点からのコスト
        int[] cost = new int[n];
        Arrays.fill(cost, Integer.MAX_VALUE);
        // 訪問済みフラグ
        boolean[] visited = new boolean[n];
        Arrays.fill(visited, false);

        // 始点
        cost[0] = 0;

        while (true) {
            // 未訪問で始点からのコストが最小の駅を探す
            int min = Integer.MAX_VALUE;
            int u = -1;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && cost[i] < min) {
                    min = cost[i];
                    u = i;
                }
            }
            if (u == -1) {
                // 全て訪問
                break;
            }
            visited[u] = true;
            // 隣接する駅までのコストを更新
            for (int i = 0; i < n; i++) {
                int w = adjacency_matrix[u][i];
                if (w > 0) {
                    int c = cost[u] + w; // 新しいコスト
                    if (c < cost[i]) {
                        cost[i] = c;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(stations[0] + " → " + stations[i] + " "
                    + cost[i] + "分");
        }
    }

}

実行結果

横浜 → 横浜 0分
横浜 → 武蔵小杉 12分
横浜 → 品川 22分
横浜 → 渋谷 25分
横浜 → 新橋 29分
横浜 → 溜池山王 33分

どっちを使うべきか

グラフの節(駅)の数をV、辺の数をEとする。

グラフが疎の場合はO(E) = O(V)となり、密の場合はO(E) = O(V^2)となる。

リストの場合と行列の場合のアルゴリズムのオーダーは次のようになる

ってことで、その場合は隣接リスト、密の場合は隣接行列が適している。