C++
初心者

初心者の忘備録 〜Dijkstra法〜

プログラミング初心者の忘備録

Dijkstra(ダイクストラ)法

  • ある固定された始点に対する他の全ての点の最短距離を求めることができる(単一始点最短路問題)
  • Bellman-Ford(ベルマンフォード)法では、明らかに最短距離ではない点や最短距離が更新されていない点でもいちいち調べるため無駄があるが、そういうことが起こらない
  • 負の辺が無いときにのみ使える
  • priority_queue(要素の追加と最小(大)値の取得が可能なデータ構造)を利用することによって、$O(|E|\log|V|)$( $|V|$ は頂点の個数、$|E|$ は辺の個数)で計算可能

具体例

http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/08.pdf#page=8 を具体例として借りさせていただきます
点Sを点0に, 点A, B, C, ... を順に点1, 2, 3, ... に置き換えます
グラフを(始点, 終点, コスト)のペアの組み合わせで表現すると以下の通り

入力
0 1 2
1 4 3
0 2 1
2 4 8
4 7 1
4 5 6
5 7 4
7 8 1
2 5 2
5 8 7
0 3 2
3 5 5
5 6 5
5 9 4
3 6 1
6 9 5
8 9 5

これをDijkstra法で解いてみます
何をやっているのか分かりやすいように各所に日本語の出力を入れています

#include <cstdio>
#include <vector>
#include <queue>
#define REP(i, n) for(int i=0;i<n;++i)
#define INF 10000000

using namespace std;

typedef pair<int, int> P;

struct edge{int to, cost;};  // toは辺の終点, costは辺のコスト

int V = 10;  // 頂点の数
int E = 17;  // 辺の数
vector<edge> G[10]; // 始点別に辺を管理

int d[10]; // 最短距離を格納

void dijkstra(int s){ // 点sを始点とする他の全ての点の最短距離を求める
    priority_queue<P, vector<P>, greater<P> > que; 
    REP(i, V) d[i] = INF;
    d[s] = 0;
    que.push(P(0, s));
    printf("点 %d への最短距離が 0 というデータを追加\n", s);

    while(!que.empty()){
        P p = que.top(); que.pop(); // 最短距離が最小値となる点が常に取り出される
        int v = p.second;
        printf("点 %d への最短距離が %d というデータを取得\n", p.second, p.first);
        if(d[v] < p.first){
            printf("・・・これは古い情報なので無視\n");
            continue;
        }
        REP(i, G[v].size()){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){ // 最短距離の更新
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
                printf("・・・点 %d への最短距離が %d というデータを追加\n", e.to, d[e.to]);
            }
        }
    }
}

int main(){
    REP(i, E){
        int f, t, c;
        scanf("%d%d%d", &f, &t, &c);
        G[f].push_back(edge{t, c});
        G[t].push_back(edge{f, c}); // 無向グラフなので双方向の辺のデータが必要
    }

    dijkstra(0);

    printf("最終結果\n");
    REP(i, V) printf("点 %d への最短距離は %d\n", i, d[i]);

    return 0;
}

すると出力はこうなります

出力
点 0 への最短距離が 0 というデータを追加
点 0 への最短距離が 0 というデータを取得
・・・点 1 への最短距離が 2 というデータを追加
・・・点 2 への最短距離が 1 というデータを追加
・・・点 3 への最短距離が 2 というデータを追加
点 2 への最短距離が 1 というデータを取得
・・・点 4 への最短距離が 9 というデータを追加
・・・点 5 への最短距離が 3 というデータを追加
点 1 への最短距離が 2 というデータを取得
・・・点 4 への最短距離が 5 というデータを追加
点 3 への最短距離が 2 というデータを取得
・・・点 6 への最短距離が 3 というデータを追加
点 5 への最短距離が 3 というデータを取得
・・・点 7 への最短距離が 7 というデータを追加
・・・点 8 への最短距離が 10 というデータを追加
・・・点 9 への最短距離が 7 というデータを追加
点 6 への最短距離が 3 というデータを取得
点 4 への最短距離が 5 というデータを取得
・・・点 7 への最短距離が 6 というデータを追加
点 7 への最短距離が 6 というデータを取得
・・・点 8 への最短距離が 7 というデータを追加
点 7 への最短距離が 7 というデータを取得
・・・これは古い情報なので無視
点 8 への最短距離が 7 というデータを取得
点 9 への最短距離が 7 というデータを取得
点 4 への最短距離が 9 というデータを取得
・・・これは古い情報なので無視
点 8 への最短距離が 10 というデータを取得
・・・これは古い情報なので無視
最終結果
点 0 への最短距離は 0
点 1 への最短距離は 2
点 2 への最短距離は 1
点 3 への最短距離は 2
点 4 への最短距離は 5
点 5 への最短距離は 3
点 6 への最短距離は 3
点 7 への最短距離は 6
点 8 への最短距離は 7
点 9 への最短距離は 7
  • priority_queue を利用することで、常にキューの中から最短距離が最も小さい点のデータを取得していること
  • 取得した点の周囲の点に関して現状の最短距離よりも距離が小さくなったら、そのデータを追加し、最短距離を更新していること
  • 更新前の最短距離のデータを取得したら、無視していること

が分かります

ちなみに点9を始点とするとこんな感じ

出力
点 9 への最短距離が 0 というデータを追加
点 9 への最短距離が 0 というデータを取得
・・・点 5 への最短距離が 4 というデータを追加
・・・点 6 への最短距離が 5 というデータを追加
・・・点 8 への最短距離が 5 というデータを追加
点 5 への最短距離が 4 というデータを取得
・・・点 4 への最短距離が 10 というデータを追加
・・・点 7 への最短距離が 8 というデータを追加
・・・点 2 への最短距離が 6 というデータを追加
・・・点 3 への最短距離が 9 というデータを追加
点 6 への最短距離が 5 というデータを取得
・・・点 3 への最短距離が 6 というデータを追加
点 8 への最短距離が 5 というデータを取得
・・・点 7 への最短距離が 6 というデータを追加
点 2 への最短距離が 6 というデータを取得
・・・点 0 への最短距離が 7 というデータを追加
点 3 への最短距離が 6 というデータを取得
点 7 への最短距離が 6 というデータを取得
・・・点 4 への最短距離が 7 というデータを追加
点 0 への最短距離が 7 というデータを取得
・・・点 1 への最短距離が 9 というデータを追加
点 4 への最短距離が 7 というデータを取得
点 7 への最短距離が 8 というデータを取得
・・・これは古い情報なので無視
点 1 への最短距離が 9 というデータを取得
点 3 への最短距離が 9 というデータを取得
・・・これは古い情報なので無視
点 4 への最短距離が 10 というデータを取得
・・・これは古い情報なので無視
最終結果
点 0 への最短距離は 7
点 1 への最短距離は 9
点 2 への最短距離は 6
点 3 への最短距離は 6
点 4 への最短距離は 7
点 5 への最短距離は 4
点 6 への最短距離は 5
点 7 への最短距離は 6
点 8 への最短距離は 5
点 9 への最短距離は 0