Dijkstra

用途

指定した頂点から他全てへの頂点への最短距離を求める. 負の辺が無いことを前提とする.

計算量

$ O(|E|\log|V|) $

Depends

DirectedGraph

使い方

宣言

1
auto res = dijkstra(g,s);

res[i]で頂点sから頂点iの最短距離を得る.

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
vector<int> dijkstra(DirectedGraph &_g,int s) {
  vector<int> d(_g.n, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
  d[s] = 0;
  que.push(make_pair(0, s));
  while (!que.empty()) {
    pair<int, int> p = que.top();
    que.pop();
    int v = p.second;
    if (d[v] < p.first)
      continue;
    for (auto e : _g.g[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(make_pair(d[e.to], e.to));
      }
    }
  }
  return d;
}