ダイクストラ法（Dijkstra）

始点から各頂点への最短距離を求める。

特徴

項目	内容
用途	単一始点最短経路
適用条件	辺の重みが非負
計算量	O((V+E) log(V+E))

実装の使い分け

• ラムダ版：単発の探索など、手軽に使いたい場合
• struct版：経路復元や複数回の探索が必要な場合

実装

軽量ラムダ版

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, int>;
const ll INFL = 1LL << 60;

struct Edge {
    int to;
    ll w;
    Edge(int to, ll w) : to(to), w(w) {}
};
using Graph = vector<vector<Edge>>;
template <class T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
    }

    vector<ll> dist(n, INFL);
    auto dijkstra = [&](int s) {
        dist[s] = 0;
        priority_queue<P, vector<P>, greater<P>> q;
        q.push({0, s});
        while (!q.empty()) {
            auto [d, v] = q.top();
            q.pop();
            if (d != dist[v]) continue;
            for (const auto& e : g[v]) {
                if (chmin(dist[e.to], d + e.w)) {
                    q.push({dist[e.to], e.to});
                }
            }
        }
    };

    dijkstra(s);

    for (int v = 0; v < n; v++) {
        if (dist[v] != INFL) cout << dist[v] << '\n';
        else cout << "INF\n";
    }
}

struct版

#pragma once
#include <algorithm>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

struct Dijkstra {
    using ll = long long;
    using P = std::pair<ll, int>;
    static constexpr ll INF = 1LL << 60;

    struct Edge {
        int to;
        ll cost;
    };
    int n;
    std::vector<std::vector<Edge>> g;
    std::vector<ll> dist;
    std::vector<int> prev;

    Dijkstra(int n) : n(n), g(n), dist(n, INF), prev(n, -1) {}

    void add_edge(int from, int to, ll cost) {
        g[from].push_back({to, cost});
    }

    void add_undirected_edge(int u, int v, ll cost) {
        add_edge(u, v, cost);
        add_edge(v, u, cost);
    }

    void build(int s) {
        dist.assign(n, INF);
        prev.assign(n, -1);
        std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
        dist[s] = 0;
        pq.push({0, s});

        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if (d != dist[v]) continue;

            for (const auto& e : g[v]) {
                ll nd = d + e.cost;
                if (nd < dist[e.to]) {
                    dist[e.to] = nd;
                    prev[e.to] = v;
                    pq.push({nd, e.to});
                }
            }
        }
    }

    // 最後のbuild()の始点からtまでの経路を復元
    // 到達不能なら空配列
    std::vector<int> get_path(int t) const {
        if (dist[t] == INF) return {};
        std::vector<int> path;
        for (int v = t; v != -1; v = prev[v]) path.push_back(v);
        std::reverse(path.begin(), path.end());
        return path;
    }
};

使用例

軽量ラムダ版

グラフとラムダ関数を定義した後に呼び出す。

dijkstra(s);
cout << dist[t] << '\n';

struct版

Dijkstra dj(4);

// 辺の追加
dj.add_edge(0, 1, 2);
dj.add_edge(0, 2, 5);
dj.add_edge(1, 2, 1);
dj.add_edge(2, 3, 4);

// 始点0からの最短距離を計算
dj.build(0);

cout << dj.dist[3] << '\n'; // 7

// 最短経路の復元
auto path = dj.get_path(3);
// path = {0, 1, 2, 3}

• add_edge(u, v, w)：有向辺を追加
• add_undirected_edge(u, v, w)：無向辺を追加
• build(s)：始点sからの最短距離を計算
• dist[v]：始点から頂点vまでの最短距離
• get_path(t)：始点から頂点tへの最短経路を復元

注意点

• 負辺がある場合は使用できない
• priority_queueに残った古い情報はスキップする
• 到達不能な頂点の距離はINFのまま
• 距離のオーバーフローに注意
• struct版のget_path()はbuild()実行後に呼ぶ

関連アルゴリズム

• BFS
• 0-1 BFS
• Bellman-Ford