ダイクストラ法

init

• 無向グラフを、頂点数\(N\)と、辺の始点と終点とコストを表現したpair<pair<int,int>,long long>のvectorとして与える。
• すると、グラフをsolve()が扱えるようになる
• 多始点などで何回も回す場合、initの実行は\(1\)回でよい
• 計算量は\(Ο(\vert E \vert)\)

Dijkstra

• コンストラクタ。initを呼ぶ

solve

• initでできたグラフに対し、与えられた\(s\)を始点としてダイクストラ法を実行する
• 得られた最小コストを要素数が\(V\)のvectorとして返す
• 計算量は\(Ο((E+V)logV)\)

github

class Dijkstra{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    typedef std::pair<long long,int> P;
    std::vector<std::vector<P>> G;
    int V;
    long long INF = (1LL<<61);
    std::priority_queue<P,std::vector<P>,std::greater<P>> que;
    
    public:
    void init(int N,std::vector<std::pair<std::pair<int,int>,long long>> edge){
        //頂点数を決定する
        V=N;
        
        //辺集合を扱いやすい形式に変換する
        G.resize(V);
        for(int i=0;i<edge.size();i++){
            int from=edge[i].first.first,to=edge[i].first.second;
            long long cost=edge[i].second;
            G[from].push_back({cost,to});
        }
    }
    
    Dijkstra(int N,std::vector<std::pair<std::pair<int,int>,long long>> edge){
        init(N,edge);
    }

    std::vector<long long> solve(int s){
        std::vector<long long> d;
        //INFで初期化する
        for(int i=0;i<V;i++){
            d.push_back(INF);
        }
        d[s]=0;
        que.push({0,s});
        //queは{cost,to}をコストが小さい順に出す
        while(!que.empty()){
            P p = que.top();
            que.pop();
            int v=p.second;
            if(d[v]<p.first)continue;
            for(int i=0;i<G[v].size();i++){
                P e = G[v][i];
                if(d[e.second]>d[v]+e.first){
                    d[e.second] = d[v]+e.first;
                    que.push({d[e.second],e.second});
                }
            }
        }
        return d;
    }
};

使用例

---

実行コード

#include <bits/stdc++.h>

class Dijkstra{/*省略*/};

int main(void){
    
    std::vector<std::pair<std::pair<int,int>,long long>> E;
    int N = 5;
    E.push_back({ {0,1},1});
    E.push_back({ {1,2},2});
    E.push_back({ {2,3},4});
    E.push_back({ {2,4},8});
    E.push_back({ {3,4},10000});
    
    Dijkstra dijkstra(N,E);
    std::vector<long long> D = dijkstra.solve(0);
    
    for(int i=0;i<N;i++){
        std::cout << D[i] << " ";
    }
    std::cout << std::endl;
    
    std::vector<long long> F = dijkstra.solve(1);
    
    for(int i=0;i<N;i++){
        std::cout << F[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

出力

0 1 3 7 11 
2305843009213693952 0 2 6 10 

更新履歴

---

日時	内容
2023/06/29	ライセンスのコメントアウトを変更
2021/03/25	使用例、コンストラクタを追加/コメントを削除
2021/02/12	バグを修正/いくつかの表記変更
2020/04/04	ダイクストラ法を追加