AtCoder で公開されている「典型アルゴリズム問題集」のD問題をC++で解いてみました。
D問題 単一始点最短経路問題
問題はリンク先をご覧ください。
グラフの始点から、すべての終点への最小移動距離を求めます。
解答案
この問題は、頂点間の移動時間（コスト） $c_i$ は、0以上の整数で与えられます。この場合は、ダイクストラ法（Dijkstra’s algorithm）が使えます。基本的な考え方は以下です。
- 頂点とコストを組にして、キューを使って処理する。
- コストが小さい順番に処理する。このため、優先度付きキューを使う場合が多くなります。
注）コストが負の値となる場合は、ベルマン-フォード法（Bellman–Ford algorithm）を使う必要があります。この記事では紹介しません。
C++ プログラム例
重み付きグラフの定番コードと考えることができます。グラフが重み付きになるため、頂点に加えて、コストも管理します（構造体 Edge）。
- 上でも述べましたが、優先度付きキューを使います（30行目）。
- キューの初期値として、始点（頂点0）を格納します（31、32行目）。
- キューが空になるまで、コストが小さい順に処理します（34ー45行目）。なお、37行目の確認が抜けていると、時間がかかる場合があります。
- dist[n-1]が求める解答になります。
以下が、C＋＋プログラムとなります。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
typedef pair<ll, int> P;
struct Edge {
int to;
ll weight;
Edge() { }
Edge(int t, ll w) : to(t), weight(w) { }
};
int main()
{
int n, m;
cin >> n >> m;
vector<vector<Edge>> G(n);
for (int i = 0; i < m; ++i) {
int u, v;
ll c;
cin >> u >> v >> c;
G[u].push_back(Edge(v, c));
}
vector<ll> dist(n, INF);
priority_queue<P, vector<P>, greater<P>> que;
dist[0] = 0;
que.push(P(0, 0));
while (!que.empty()) {
P p = que.top();
que.pop();
int now = p.second;
if (dist[now] < p.first) {
continue;
}
for (auto next_v : G[now]) {
if (dist[next_v.to] > dist[now] + next_v.weight) {
dist[next_v.to] = dist[now] + next_v.weight;
que.push(P(dist[next_v.to], next_v.to));
}
}
}
cout << dist[n - 1] << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
何回か紹介したダイクストラ法の復習ができました。ある意味貪欲法ですが、応用範囲が広いアルゴリズムだと考えています。
この問題集は、わたくしには、ちょうど良い難易度でした。引き続き解答案を紹介していきます。
