【第13回】Dijsktra法

Dijsktra法を紹介します

Homeブログ一覧【第13回】Dijsktra法

Dijkstra法(ダイクストラ法)

  • 重み付きグラフの最短経路を求めるアルゴリズム。
  • 始点からの最短距離を求める。
  • 辺の重みが負でない場合に使える。
  • 今回は優先度付きキューを使って実装する。
  • 同じく最短経路を考えるBFSは重みの無い(もしくは重みの等しい)グラフにしか用いることができなかったが、Dijkstra法は重みが辺ごとに違うグラフにも対応できる。
優先度付きキュー
  • 優先度付きキューは、入れた順番ではなく、優先度の高い順に取り出すデータ構造。
  • C++ではpriority_queueを使う。
  • priority_queueはデフォルトで降順になるので、昇順にする場合はgreaterを使う。
priority_queue<int> q; //降順
priority_queue<int,vector<int>,greater<int>> q; //昇順
q.top(); //最大値(昇順なら最小値)
q.pop(); //最大値(昇順なら最小値)を取り出す
q.push(1); //要素(ここでは1)を追加

実装テンプレート

#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
  ll n, m;
  cin >> n >> m;                      // n:頂点数 m:辺数
  vector<vector<pair<ll, ll>>> g(n);  // g[i]:iから出る辺の行き先と重み
  rep(i, m) {                         // 辺の入力
    ll a, b, c;
    cin >> a >> b >> c;  // a:始点 b:終点 c:重み
    a--, b--;                     // 0-indexedにする
    g[a].push_back({b, c});  // aからbへの重みcの辺を追加
    g[b].push_back({a, c});  // bからaへの重みcの辺を追加
  }
  vector<ll> dist(n, 1e18);  // dist[i]:頂点iへの最短距離
  dist[0] = 0;               // 始点は0
  // (最短距離,頂点)を昇順にする優先度付きキュー
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
  q.push({0, 0});       // 始点を追加
  while (!q.empty()) {  // qが空になるまでくりかえす
    auto [d, v] = q.top();
    q.pop();                          // 最短距離の頂点を取り出す
    if (dist[v] < d) continue;        // 最短距離でないならスキップ
    for (auto [nv, nd] : g[v]) {      // vから出る辺をすべて見る
      if (dist[nv] > dist[v] + nd) {  // 最短距離を更新できるなら更新
        dist[nv] = dist[v] + nd;      // 最短距離を更新
        q.push({dist[nv], nv});       // 更新した頂点を追加
      }
    }
  }
  cout << dist[n - 1] << endl;  // 頂点n-1への最短距離を出力
}
  • この記事にもDijkstra法の解説があります。一つ一つの処理を理解するのに役立ちます。

例題

ヒント
  • テンプレを書き換えると解けます。
  • 始点に注意して、どう動いているのか確認しながら解いてみてください。
解答例
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
  ll n, m, r;
  cin >> n >> m >> r;                 // n:頂点数 m:辺数 r:始点
  vector<vector<pair<ll, ll>>> g(n);  // g[i]:iから出る辺の行き先と重み
  rep(i, m) {                         // 辺の入力
    ll a, b, c;
    cin >> a >> b >> c;      // a:始点 b:終点 c:重み
    g[a].push_back({b, c});  // aからbへの重みcの辺を追加
  }
  vector<ll> dist(n, 1e18);  // dist[i]:頂点iへの最短距離
  dist[r] = 0;               // 始点は0
  // (最短距離,頂点)を昇順にする優先度付きキュー
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
  q.push({0, r});       // 始点を追加
  while (!q.empty()) {  // qが空になるまでくりかえす
    auto [d, v] = q.top();
    q.pop();                          // 最短距離の頂点を取り出す
    if (dist[v] < d) continue;        // 最短距離でないならスキップ
    for (auto [nv, nd] : g[v]) {      // vから出る辺をすべて見る
      if (dist[nv] > dist[v] + nd) {  // 最短距離を更新できるなら更新
        dist[nv] = dist[v] + nd;      // 最短距離を更新
        q.push({dist[nv], nv});       // 更新した頂点を追加
      }
    }
  }
  rep(i, n) {
    if (dist[i] < 1e18)
      cout << dist[i] << endl;  // 頂点n-1への最短距離を出力
    else
      cout << "INF" << endl;  // 頂点n-1への最短距離が存在しないならINFを出力
  }
}

演習問題

【第12回】グラフの復習とUnion-Find

【第14回】動的計画法(DP)　その1