Dijkstra's Algorithm (ダイクストラ法)
(graph/dijkstra.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-07-14 19:47:52+09:00
• Include: #include "graph/dijkstra.hpp"

Dijkstra’s Algorithm (ダイクストラ法)

概要

単一始点最短経路問題を解くことができるアルゴリズムです。
やきとりくんを参考にしました。ありがとうございます。

使い方

• dijkstra(G, x): グラフ $G$ における $x$ を始点とするそれぞれの頂点への最短距離を求めます。
• shortest_path(G, s, t): グラフ $G$ における $s$ から $t$ への最短パスを求めます。

計算量

頂点数を $V$、辺の数を $E$ とすると、

• dijkstra(G, x): $O((E + V) \log V)$
• shortest_path(G, s, t): $O((E + V) \log V)$

Code

#pragma once
/**
 * @brief Dijkstra's Algorithm (ダイクストラ法)
 * 
 */

template <typename T>
vector<long long> dijkstra(const vector<vector<array<long long, 2>>> &G, T x){
    const long long INF = 9e18 / 2;
    vector<long long> cost((int) G.size(), INF);
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<>> q;
    cost[x] = 0;
    q.emplace(0, x);
    
    while(q.size()){
        auto [c, at] = q.top();
        q.pop();
        if(c > cost[at]) continue;
        for(auto& [to, t] : G[at]){
            if(cost[to] > c + t){
                cost[to] = c + t;
                q.emplace(cost[to], to);
            }
        }
    }
    return cost;
}

pair<long long, vector<pair<int, int>>> shortest_path(const vector<vector<array<long long, 2>>> &G, int s, int t){
    const long long INF = 9e18 / 2;
    vector<long long> cost((int) G.size(), INF);
    vector<int> par((int) G.size(), -1);
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<>> q;
    cost[s] = 0;
    par[s] = -1;
    q.emplace(0, s);

    while(q.size()){
        auto [c, at] = q.top();
        q.pop();
        if(c > cost[at]) continue;
        for(auto& [to, t] : G[at]){
            if(cost[to] > c + t){
                par[to] = at;
                cost[to] = c + t;
                q.emplace(cost[to], to);
            }
        }
    }

    if(cost[t] == INF){
        return {-1, {}};
    }
    vector<pair<int, int>> path;
    int now = t;
    while(par[now] != -1){
        path.emplace_back(par[now], now);
        now = par[now];
    }
    reverse(path.begin(), path.end());

    return {cost[t], path};
}

#line 2 "graph/dijkstra.hpp"
/**
 * @brief Dijkstra's Algorithm (ダイクストラ法)
 * 
 */

template <typename T>
vector<long long> dijkstra(const vector<vector<array<long long, 2>>> &G, T x){
    const long long INF = 9e18 / 2;
    vector<long long> cost((int) G.size(), INF);
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<>> q;
    cost[x] = 0;
    q.emplace(0, x);
    
    while(q.size()){
        auto [c, at] = q.top();
        q.pop();
        if(c > cost[at]) continue;
        for(auto& [to, t] : G[at]){
            if(cost[to] > c + t){
                cost[to] = c + t;
                q.emplace(cost[to], to);
            }
        }
    }
    return cost;
}

pair<long long, vector<pair<int, int>>> shortest_path(const vector<vector<array<long long, 2>>> &G, int s, int t){
    const long long INF = 9e18 / 2;
    vector<long long> cost((int) G.size(), INF);
    vector<int> par((int) G.size(), -1);
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<>> q;
    cost[s] = 0;
    par[s] = -1;
    q.emplace(0, s);

    while(q.size()){
        auto [c, at] = q.top();
        q.pop();
        if(c > cost[at]) continue;
        for(auto& [to, t] : G[at]){
            if(cost[to] > c + t){
                par[to] = at;
                cost[to] = c + t;
                q.emplace(cost[to], to);
            }
        }
    }

    if(cost[t] == INF){
        return {-1, {}};
    }
    vector<pair<int, int>> path;
    int now = t;
    while(par[now] != -1){
        path.emplace_back(par[now], now);
        now = par[now];
    }
    reverse(path.begin(), path.end());

    return {cost[t], path};
}

Back to top page