ダイクストラ法

要点

ダイクストラ法は、未確定頂点のうち距離が最小の頂点を順に確定する。辺重みがすべて非負なら、確定後により短い経路が現れない。

計算量

二分ヒープを使うと、頂点数を $V$、辺数を $E$ として

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

となる。多くの連結グラフでは $O(E\log V)$ と書いてよい。

実装

using P = pair<long long, int>;
vector<long long> dijkstra(const vector<vector<pair<int,int>>>& g, int s) {
    const long long INF = 1LL << 60;
    vector<long long> dist(g.size(), INF);
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
        auto [d, v] = que.top(); que.pop();
        if (d != dist[v]) continue;
        for (auto [to, cost] : g[v]) {
            if (dist[to] > d + cost) {
                dist[to] = d + cost;
                que.emplace(dist[to], to);
            }
        }
    }
    return dist;
}

古い要素を削除せず、取り出した距離が現在値と違えば無視する。この方針では decrease-key が不要になる。グラフを木として扱える問題では 木の基本的な走査 も参照する。

よくある誤り

• 距離を int にしてオーバーフローする
• 無向辺の逆向きを追加し忘れる
• 到達不能を表す INF に辺重みを加える