Dijkstra - ダイクストラ法
(Library/Graph/Dijkstra.hpp)

View this file on GitHub
Last update: 2026-02-13 15:23:31+09:00
Include: #include "Library/Graph/Dijkstra.hpp"

Dijkstra - ダイクストラ法

頂点数 $V$ 辺数 $E$ のグラフにおける単一始点最短経路問題をダイクストラ法を用いて解きます。

Function

Constructor

Dijkstra(Graph<WeightType> &graph, Vertex s = -1)

グラフ $G$ を頂点数 $V$ 辺数 $E$ の graph で初期化します。
始点頂点 $s$ を指定すると、初期化後に Solve(s) を呼び出します。

制約

$-1 \le s \lt V$

計算量

$\textrm{O}(V)$

Reachable

inline bool Reachable(const Vertex &t) const

頂点 $s$ から頂点 $t$ に到達可能であるかを判定します。

制約

$0 \le t \lt V$
Solve() が $1$ 回以上呼び出されている

計算量

$\textrm{O}(1)$

Distance

inline WeightType Distance(const Vertex &t) const

頂点 $s$ から頂点 $t$ への最短経路長を返します。
頂点 $t$ に到達不能であるとき、INF を返します。

制約

$0 \le t \lt V$
Solve() が $1$ 回以上呼び出されている

計算量

$\textrm{O}(1)$

Path

vector<Edge<WeightType>> Path(const Vertex &t) const

頂点 $s$ から頂点 $t$ への最短経路を辺の列として返します。
最短経路が複数ある場合、そのうちの $1$ つを返します。
頂点 $t$ に到達不能であるとき空列を返します。

制約

$0 \le t \lt V$
Solve() が $1$ 回以上呼び出されている

計算量

$\textrm{O}(V)$

Solve

void Solve(Vertex s)

頂点 $s$ を始点とした単一始点最短経路問題を解きます。

制約

$0 \le s \lt V$

計算量

$\textrm{O}((V + E) \log V)$

operator[]

(1) WeightType operator[](const Vertex &t)
(2) const WeightType operator[](const Vertex &t) const 

Distance(t) を返します。

制約

$0 \le t \lt V$
Solve(s) が $1$ 回以上呼び出されている

計算量

$\textrm{O}(1)$

Depends on

Verified with

Code

#pragma once

#include "Graph.hpp"

template<typename WeightType>
class Dijkstra{
    public:
    Dijkstra(Graph<WeightType> &graph, Vertex s = -1) :
        G(graph), V(graph.VertexSize()), dist_(V), prev_edge_(V){
        if(s != -1) Solve(s);
    }

    inline bool Reachable(const Vertex &t) const {
        return dist_[t] != inf;
    }

    inline WeightType Distance(const Vertex &t) const {
        return dist_[t];
    }

    vector<Edge<WeightType>> Path(const Vertex &t) const {
        if(!Reachable(t)) return vector<Edge<WeightType>>{};
        vector<Edge<WeightType>> ret;
        int v = t;
        while(1){
            if(prev_edge_[v].from == -1) break;
            ret.push_back(prev_edge_[v]);
            v = prev_edge_[v].from;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    void Solve(Vertex s){
        using P = pair<WeightType, Vertex>;
        fill(dist_.begin(), dist_.end(), inf);
        dist_[s] = WeightType(0);
        fill(prev_edge_.begin(), prev_edge_.end(), Edge<WeightType>{});
        prev_edge_[s] = Edge<WeightType>(-1, -1);
        priority_queue<P, vector<P>, greater<P>> que;
        que.emplace(WeightType(0), s);
        while(que.size()){
            auto [d, u] = que.top(); que.pop();
            if(dist_[u] != d) continue;
            for(const Edge<WeightType> &e : G[u]){
                if(dist_[e.to] > d + e.cost){
                    dist_[e.to] = d + e.cost;
                    prev_edge_[e.to] = e;
                    que.emplace(dist_[e.to], e.to);
                }
            }
        }
    }

    inline WeightType operator[](const Vertex &v){
        return dist_[v];
    }

    inline const WeightType operator[](const Vertex &v) const {
        return dist_[v];
    }

    private:
    Graph<WeightType> &G;
    int V;
    Vertex source_;
    WeightType inf{WeightType(INF)};
    vector<WeightType> dist_;
    vector<Edge<WeightType>> prev_edge_;
};

#line 2 "Library/Graph/Dijkstra.hpp"

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 4 "Library/Graph/Dijkstra.hpp"

template<typename WeightType>
class Dijkstra{
    public:
    Dijkstra(Graph<WeightType> &graph, Vertex s = -1) :
        G(graph), V(graph.VertexSize()), dist_(V), prev_edge_(V){
        if(s != -1) Solve(s);
    }

    inline bool Reachable(const Vertex &t) const {
        return dist_[t] != inf;
    }

    inline WeightType Distance(const Vertex &t) const {
        return dist_[t];
    }

    vector<Edge<WeightType>> Path(const Vertex &t) const {
        if(!Reachable(t)) return vector<Edge<WeightType>>{};
        vector<Edge<WeightType>> ret;
        int v = t;
        while(1){
            if(prev_edge_[v].from == -1) break;
            ret.push_back(prev_edge_[v]);
            v = prev_edge_[v].from;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    void Solve(Vertex s){
        using P = pair<WeightType, Vertex>;
        fill(dist_.begin(), dist_.end(), inf);
        dist_[s] = WeightType(0);
        fill(prev_edge_.begin(), prev_edge_.end(), Edge<WeightType>{});
        prev_edge_[s] = Edge<WeightType>(-1, -1);
        priority_queue<P, vector<P>, greater<P>> que;
        que.emplace(WeightType(0), s);
        while(que.size()){
            auto [d, u] = que.top(); que.pop();
            if(dist_[u] != d) continue;
            for(const Edge<WeightType> &e : G[u]){
                if(dist_[e.to] > d + e.cost){
                    dist_[e.to] = d + e.cost;
                    prev_edge_[e.to] = e;
                    que.emplace(dist_[e.to], e.to);
                }
            }
        }
    }

    inline WeightType operator[](const Vertex &v){
        return dist_[v];
    }

    inline const WeightType operator[](const Vertex &v) const {
        return dist_[v];
    }

    private:
    Graph<WeightType> &G;
    int V;
    Vertex source_;
    WeightType inf{WeightType(INF)};
    vector<WeightType> dist_;
    vector<Edge<WeightType>> prev_edge_;
};

Dijkstra - ダイクストラ法 (Library/Graph/Dijkstra.hpp)

Dijkstra - ダイクストラ法

Function

Constructor

Reachable

Distance

Path

Solve

operator[]

Depends on

Verified with

Code

Dijkstra - ダイクストラ法
(Library/Graph/Dijkstra.hpp)