Dijkstra法

ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

引用元　https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95

利用するポイント

• 辺の重みが非負
  • 0でもいいらしい。

実装のポイント

• costが最小の頂点から探索するのでpriority_queueを利用する

サンプルコード　abc340-D

# include <iostream>
# include <vector>
# include <utility>
# include <queue>

using namespace std;
using ll = long long;
const ll INF=1e18;

int main(){
    // INPUT
    int n; cin >> n;
    vector<ll> a(n), b(n), x(n);
    for(int i=0; i<n-1; ++i) {
        cin >> a[i] >> b[i] >> x[i];
        x[i]--;
    }

    // g[i] 接続しているノードのlist
    // pair<next_node, cost>
    vector<vector<pair<ll, ll> > > g(n);
    for(ll i=0; i<n-1; ++i) {
        g[i].push_back({i+1, a[i]});
        g[i].push_back({x[i], b[i]});
    }

    vector<ll> dist(n, INF); // distanceはINFで初期化する　→　より小さいdistを発見したら更新
    dist[0] = 0; // 初期ノードは重みゼロ
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
    // 確定していない頂点のうち最小コストの頂点を探索するのでpriority_queueを使って最小コストの頂点を前に格納する
    que.push({dist[0], 0});

    while(!que.empty()) {
        int d;
        ll v;
        tie(d, v) = que.top();
        que.pop();
        if(d > dist[v]) continue;
        for(auto nv : g[v]) {
            ll cost = nv.second;
            int nd = nv.first;
            if(dist[nd] > cost + dist[v]) {
                dist[nd] = cost + dist[v];
                que.push({dist[nd], nd});
            }
        }
    }

    cout << dist[n-1] << endl;
    return 0;
}  

出題例

疑問

• 閉路があっても大丈夫なのか？
  • 辺の重みが正数であれば探索しないので大丈夫だろう。
  • 辺の重み0の閉路があっても、queueの後ろにpushしているから大丈夫なのかも。
• 単一始点であることは必須なのか？
  • queueを初期化するときに複数のノードをpushしてもいい気がする。
• グラフの有向・無向は議題になっていない
  • 実装のときに有向グラフも無向グラフも対応できそう。

課題

• 辺の重みに負数があるときの対応（ベルマンフォード法というものがあるらしい）