Algoogle

Algorithm for Programming Contest

Dijkstra法

基本情報


計算量
用途 負辺のないグラフで単一始点最短路を求める.

E := 辺の数
V := 頂点の数

解説


負辺の無いグラフで始点が決まっている時, その点からグラフ上の各頂点までの最短距離を求めることができる.
Dijkstra法ではまだ調べていない頂点のうち, 始点から一番近い点を順に見ていき, その点からいける点の最短距離を更新していく.
負辺がないのですでに調べている点はこれによって更新されることはなく, したがって順に最短路を求めることができる.

まだ調べていない頂点のうち一番近い点というのは, 到達したかどうかのメモとpriority_queueなどのデータ構造を使うことで効率よく求めることができる.

またpriority_queueは値が大きいものが基本的に優先されるので, greaterを指定して小さい方から取ってこさせるか, コードのように比較の不等号の意味を逆に定義させる.

コード

(dijkstra.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct node {
    int v, d;
    node(int v, int d):v(v),d(d){}
    bool operator<(const node &n) const { return d > n.d; }
};
struct edge { int to, d; };
int V;
vector<edge> G[MAX];
int dist[MAX]; // shortest distance

void dijkstra(int s) {
    memset(dist, -1, sizeof(dist));
    priority_queue<node> que;
    que.push(node(s, 0));
    while(!que.empty()){
        int v = que.top().v, d = que.top().d;
        que.pop();
        if(dist[v] >= 0 and dist[v] <= d) continue;
        dist[v] = d;
        for(int i = 0; i < G[v].size(); i++)
            que.push(node(G[v][i].to, d+G[v][i].d));
    }
}

問題


Comments