Dijkstra 法
(graph/dijkstra.hpp)

• View this file on GitHub
• Last update: 2022-09-03 17:27:23+09:00
• Include: #include "graph/dijkstra.hpp"

概要

• Dijkstra 法で単一始点最短路を求める。

使い方

• dijkstra(s, g): 重み付きグラフ g における、頂点 s から全点間の最短距離を求める。g は (to, cost) のペアを持つ隣接リスト。(dist, from) を返す。

Verified with

• test/library-checker/shortest_path.test.cpp

Code

#pragma once
#include <limits>
#include <queue>
#include <vector>
template <typename T>
std::pair<std::vector<T>, std::vector<int>> dijkstra(
    int s, const std::vector<std::vector<std::pair<int, T>>> &g) {
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                        std::greater<std::pair<T, int>>>
        que;
    int n = int(g.size());
    std::vector<T> d(n, std::numeric_limits<T>::max());
    std::vector<int> from(n, -1);
    d[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
        auto [dist, pos] = que.top();
        que.pop();
        if (d[pos] < dist) continue;
        for (auto [to, cost] : g[pos]) {
            if (d[pos] + cost < d[to]) {
                d[to] = d[pos] + cost;
                from[to] = pos;
                que.emplace(d[to], to);
            }
        }
    }
    return {d, from};
}

#line 2 "graph/dijkstra.hpp"
#include <limits>
#include <queue>
#include <vector>
template <typename T>
std::pair<std::vector<T>, std::vector<int>> dijkstra(
    int s, const std::vector<std::vector<std::pair<int, T>>> &g) {
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                        std::greater<std::pair<T, int>>>
        que;
    int n = int(g.size());
    std::vector<T> d(n, std::numeric_limits<T>::max());
    std::vector<int> from(n, -1);
    d[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
        auto [dist, pos] = que.top();
        que.pop();
        if (d[pos] < dist) continue;
        for (auto [to, cost] : g[pos]) {
            if (d[pos] + cost < d[to]) {
                d[to] = d[pos] + cost;
                from[to] = pos;
                que.emplace(d[to], to);
            }
        }
    }
    return {d, from};
}

Back to top page