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

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

概要

ヒープを使わないダイクストラ法．密なグラフではこっちの方が高速．

計算量

$O(V^2)$

実装

std::vector<Weight> dijkstra(const Graph &g, int s) {
    static const Weight INF = std::numeric_limits<Weight>::max() / 8;
    const size_t n = g.size();
    Matrix m(n, Array(n, INF));
    for (const Edges &es : g)
        for (const Edge &e : es) m[e.src][e.dst] = std::min(m[e.src][e.dst], e.weight);
    std::vector<Weight> d(n, INF);
    std::vector<int> used(n);
    d[s] = 0;
    while (1) {
        int v = -1;
        for (size_t j = 0; j < n; j++)
            if (!used[j] && (v == -1 || d[j] < d[v])) v = j;
        if (v == -1) break;
        used[v] = true;
        /* if(v == t) return d[v]; */
        for (const Edge &e : g[v]) {
            int u = e.dst;
            d[u] = std::min(d[u], d[v] + m[v][u]);
        }
    }
    return d;
}