dijkstra (simple ver)
(src/graph/simple/dijkstra.hpp)

• View this file on GitHub
• Last update: 2022-12-06 04:57:33+09:00
• Include: #include "src/graph/simple/dijkstra.hpp"

概要

辺の重みが非負数であるグラフ $G(V, E)$ の最短経路問題を解きます。

最短経路木の情報が欲しい場合はsrc/graph/Dijkstra.hppを使ってください。

機能

std::vector<cost_type> dijkstra(const std::vector<std::vector<std::pair<int, cost_type>>>& G, 
int s, cost_type inf = std::numeric_limits<cost_type>::max())

• テンプレート引数: 辺の重みの型
  • int、long、long long以外での使用を想定していません
• G: グラフの隣接リストを表す二次元vector
  • G[i][j] (std::pair<int, cost_type>): 頂点iからG[i][j].firstにコストG[i][j].secondの有向辺が存在する。
  • AtCoderだったらzawa::read_weighted_graph<cost_type>で標準入力から対応する隣接リストを作れます。（有向・無向に注意）

• s: 最短経路を求めたい始点

• inf: テーブルの初期値
  • 基本自分で指定してください。std::numeric_limits<cost_type>::max()がデフォルトで指定されていますが、そのまま使うのはオーバーフローが怖かったり、非連結の時の処理にだるかったりすると思います。

• 返り値: res[i]には始点sから頂点iへの最短経路の総コストが入っています。s からiに到達不可能な場合、infが入っています。

• 計算量: $O((\mid V \mid + \mid E \mid)\log (\mid V \mid))$

Verified with

• test/simple-dijkstra1.test.cpp
• test/simple-dijkstra2.test.cpp

Code

#pragma once

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class cost_type>
std::vector<cost_type> dijkstra(const std::vector<std::vector<std::pair<int, cost_type>>>& G, 
        int s, cost_type inf = std::numeric_limits<cost_type>::max()) {
    std::vector<cost_type> res(G.size(), inf);
    res[s] = 0;
    std::priority_queue<
        std::pair<cost_type, int>, 
        std::vector<std::pair<cost_type, int>>, 
        std::greater<std::pair<cost_type, int>>
            > que;
    que.push({ 0, s }); 
    while (que.size()) {
        auto [d, v] = que.top();
        que.pop();
        if (d > res[v]) {
            continue;
        }
        for (auto [x, w] : G[v]) {
            if (res[x] > d + w) {
                res[x] = d + w;
                que.push({ d + w, x });
            }
        }
    }
    return res;
}

} // namespace zawa

#line 2 "src/graph/simple/dijkstra.hpp"

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class cost_type>
std::vector<cost_type> dijkstra(const std::vector<std::vector<std::pair<int, cost_type>>>& G, 
        int s, cost_type inf = std::numeric_limits<cost_type>::max()) {
    std::vector<cost_type> res(G.size(), inf);
    res[s] = 0;
    std::priority_queue<
        std::pair<cost_type, int>, 
        std::vector<std::pair<cost_type, int>>, 
        std::greater<std::pair<cost_type, int>>
            > que;
    que.push({ 0, s }); 
    while (que.size()) {
        auto [d, v] = que.top();
        que.pop();
        if (d > res[v]) {
            continue;
        }
        for (auto [x, w] : G[v]) {
            if (res[x] > d + w) {
                res[x] = d + w;
                que.push({ d + w, x });
            }
        }
    }
    return res;
}

} // namespace zawa

Back to top page