二分ヒープによるダイクストラ法 (Dijkstra’s Algorithm with Binary Heap)

概要

単一始点最短経路問題(SSSP)を解くアルゴリズム。 到達するまでのコストが小さい方からコストを伝搬させていく。

負閉路を含まないグラフに対して適用できる。

計算量

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

実装

#include<vector>
#include<queue>
using namespace std;
using ll = long long;


#define N 100003
const ll inf = 1e10;

struct Node {
  ll cost; int v;

  bool operator>(const Node &other) const { return cost > other.cost; }
};
using p_queue = priority_queue<Node, vector<Node>, greater<Node> >;

struct Edge {
  int to; ll cost;
};
vector<Edge> g[N]; // 入力: グラフG

int n;
ll dist[N]; // 出力: 各頂点vの距離dist[v]

// 始点sから各頂点までの距離を計算
void dijkstra(int s) {
  p_queue que;
  que.emplace(Node{0, s});
  for(int i=0; i<n; ++i) dist[i] = inf;
  dist[s] = 0;

  while(!que.empty()) {
    Node nd = que.top();
    ll co = nd.cost; int v = nd.v;
    que.pop();
    if(dist[v] < co) continue;
    for(auto &e : g[v]) {
      if(co + e.cost < dist[e.to]) {
        dist[e.to] = co + e.cost;
        que.emplace(Node{dist[e.to], e.to});
      }
    }
  }
}

Verified

  • AOJ: "GRL_1_A: Shortest Path - Single Source Shortest Path": source (C++14, 0.13sec)