Home > libalgo > 単一始点最短路 (Dijkstra; Heap)

単一始点最短路 (Dijkstra; Heap)

概要

単一始点最短経路問題を解くアルゴリズム．負辺があるとやり直しが発生し，最悪負のループがあると終了しないため，ベルマンフォードを使うこと．下の実装は優先度付きキューを利用している．

使い方

密なグラフでは $O(n^2)$ の実装 (graph/dijkstra-matrix.cc) を使うべき．負辺は計算量に影響し，最悪無限ループ．

計算量

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

実装

std::vector<Weight> dijkstra(const Graph &g, int s) {
    const Weight INF = std::numeric_limits<Weight>::max() / 8;
    using state = std::tuple<Weight, int>;
    std::priority_queue<state> q;
    std::vector<Weight> dist(g.size(), INF);
    dist[s] = 0;
    q.emplace(0, s);
    while (q.size()) {
        Weight d;
        int v;
        std::tie(d, v) = q.top();
        q.pop();
        d *= -1;
        /* if(v == t) return d; */
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    return dist;
}