---
title: ダイクストラ法で単一始点最短経路計算
tags: []
categories: ["Programming", "Algorithm", "Search", "Dijkstra"]
date: 2011-07-22T19:01:18Z
updated: 2011-07-22T19:01:18Z
---

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

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

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

<img src="/api/v1/files/00029/graph.png" width="500" />

### 隣接リスト

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


`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)`となる。

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

<table>
<tr><th></th><th>隣接リスト</th><th>隣接行列</th></tr>
<tr><th>疎</th><td><code>O((E+V)logV) = O(VlogV)</code></td><td><code>O(V^2+E) = O(V^2)</code></td></th>
<tr><th>密</th><td><code>O((E+V)logV) = O(V^2logV)</code></td><td><code>O(V^2+E) = O(V^2)</code></td></th>
</table>

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