ダイクストラ法
(graph/shortestpath/dijkstra.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/shortestpath/dijkstra.hpp"

概要

単一始点最短路. 辺の重みが非負である必要がある.

計算量

$O(E\log V)$

使用例

• dijkstra(g, frm) : frmからダイクストラ法.
  • 返り値の型 : vector<T>

Verified with

• test/aoj/GRL_1_A.test.cpp
• test/yukicoder/20.test.cpp

Code

/**
* @brief ダイクストラ法
* @docs docs/graph/shortestpath/dijkstra.md
*/

template <typename T>
vector<T> dijkstra(const Graph<T>& g, int frm) {
    using P = pair<T, int>;
    vector<T> ret(g.V, GINF<T>);
    ret[frm] = 0;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(ret[frm], frm);
    while (not pq.empty()) {
        T cst;
        int idx;
        tie(cst, idx) = pq.top();
        pq.pop();
        if (ret[idx] < cst) continue;
        for (auto& e : g.mat[idx]) {
            T nxt_cst = cst + e.cst;
            if (ret[e.to] <= nxt_cst) continue;
            ret[e.to] = nxt_cst;
            pq.emplace(ret[e.to], e.to);
        }
    }
    return ret;
}

#line 1 "graph/shortestpath/dijkstra.hpp"
/**
* @brief ダイクストラ法
* @docs docs/graph/shortestpath/dijkstra.md
*/

template <typename T>
vector<T> dijkstra(const Graph<T>& g, int frm) {
    using P = pair<T, int>;
    vector<T> ret(g.V, GINF<T>);
    ret[frm] = 0;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(ret[frm], frm);
    while (not pq.empty()) {
        T cst;
        int idx;
        tie(cst, idx) = pq.top();
        pq.pop();
        if (ret[idx] < cst) continue;
        for (auto& e : g.mat[idx]) {
            T nxt_cst = cst + e.cst;
            if (ret[e.to] <= nxt_cst) continue;
            ret[e.to] = nxt_cst;
            pq.emplace(ret[e.to], e.to);
        }
    }
    return ret;
}

Back to top page