Dijkstra (ダイクストラ法)
(src/graph/Dijkstra.hpp)

• View this file on GitHub
• Last update: 2022-11-02 17:08:10+09:00
• Include: #include "src/graph/Dijkstra.hpp"

概要

zawa::Dijkstra<COST>(n)

$n$ 頂点のグラフについて単一始点最短経路を求めます。

std::priority_queueを利用しています。

• (TODO:フィボナッチヒープ版も作ってみる)

機能

• コンストラクタ: COSTには重みの型を入れてください
• add_edge(int from, int to, COST cost): from から to へ重みcostの有向辺を追加します。追加された辺の番号を返します。
• get_edge(int id): id番目(0-indexed)に追加された辺を返します。int from, int to, COST costからなるedge構造体です。
• build(int s): 始点sから他全ての頂点への最短経路を求めます。
• inf(): std::numeric_limits<COST>::max()を返します。始点sから到達できない頂点vに対してdist_v = inf()です。
• get_dist(int v): 頂点vまでの最短経路のコストを返します
• get_prev(int v): 最短経路木について、vの親を返します。始点（根）sは-1が返ります
• get_route(int v): 最短経路木について、vの親と自身を繋ぐ辺の番号を返します。sに対しては-1が返ります。

計算量

• build: $O((\mid V\mid + \mid E \mid) \log( \mid V\mid))$

Verified with

• test/Dijkstra1.test.cpp
• test/Dijkstra2.test.cpp
• test/Dijkstra3.test.cpp

Code

#pragma once

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class COST>
class Dijkstra {
public:
    Dijkstra(std::size_t n) 
        : G(n) 
        , dist(n, _inf) 
        , prevs(n, -1) 
        , route(n, -1) {}

    struct edge {
        int from, to;
        COST cost;
    };

    int add_edge(int from, int to, COST cost) {
        int res = (int)edges.size();
        edges.push_back({ from, to, cost });
        G[from].emplace_back(res);
        return res;
    }

    edge get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        using pci = std::pair<COST, int>;
        dist[s] = 0;
        std::priority_queue<pci, std::vector<pci>, std::greater<pci>> que;
        que.emplace(0, s);
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (dist[v] < d) {
                continue;
            }
            for (auto id : G[v]) {
                edge e = edges[id];
                if (dist[e.to] > d + e.cost) {
                    dist[e.to] = d + e.cost;
                    prevs[e.to] = v;
                    route[e.to] = id;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
    }

    COST inf() {
        return _inf;
    }

    COST get_dist(int v) {
        return dist[v];
    }

    int get_prev(int v) {
        return prevs[v];
    }

    int get_route(int v) {
        return route[v];
    }

private:
    static constexpr COST _inf = std::numeric_limits<COST>::max();
    std::vector<edge> edges;
    std::vector<std::vector<int>> G; 
    std::vector<COST> dist;
    std::vector<int> prevs;
    std::vector<int> route;
};

} // namespace zawa

#line 2 "src/graph/Dijkstra.hpp"

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class COST>
class Dijkstra {
public:
    Dijkstra(std::size_t n) 
        : G(n) 
        , dist(n, _inf) 
        , prevs(n, -1) 
        , route(n, -1) {}

    struct edge {
        int from, to;
        COST cost;
    };

    int add_edge(int from, int to, COST cost) {
        int res = (int)edges.size();
        edges.push_back({ from, to, cost });
        G[from].emplace_back(res);
        return res;
    }

    edge get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        using pci = std::pair<COST, int>;
        dist[s] = 0;
        std::priority_queue<pci, std::vector<pci>, std::greater<pci>> que;
        que.emplace(0, s);
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (dist[v] < d) {
                continue;
            }
            for (auto id : G[v]) {
                edge e = edges[id];
                if (dist[e.to] > d + e.cost) {
                    dist[e.to] = d + e.cost;
                    prevs[e.to] = v;
                    route[e.to] = id;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
    }

    COST inf() {
        return _inf;
    }

    COST get_dist(int v) {
        return dist[v];
    }

    int get_prev(int v) {
        return prevs[v];
    }

    int get_route(int v) {
        return route[v];
    }

private:
    static constexpr COST _inf = std::numeric_limits<COST>::max();
    std::vector<edge> edges;
    std::vector<std::vector<int>> G; 
    std::vector<COST> dist;
    std::vector<int> prevs;
    std::vector<int> route;
};

} // namespace zawa

Back to top page