ブログにKaTeXを導入したので、早速数式を使った記事を書きました。👍
記念すべき？アルゴリズム系記事の第一弾で、題材は単一始点最短経路問題のまとめです。
Notice: 記事中のコードはC++です。基本的にアルゴリズム関連の記事のコードはC++で書いていきます。
...実のところこの記事自体はもともと旧ブログで書いていたもので、そこからサルベージしてきてちょっと修正したものです。😅
前提知識:
- Big-O
- グラフ関連の用語
- 隣接行列
- 隣接リスト
- ...くらい
単一始点最短経路問題とは
Single Source Shortes Path: SSSP
あるグラフについて、決められた一つの頂点から他のすべての頂点への最短経路を求める問題のこと。
（ここで最短経路とは、ある二つの頂点を繋ぐ経路のうちで最も通る辺のコストの和が小さい経路のこと。）
単一始点最短経路の性質
- 経路上に負の閉路が存在する場合、好きなだけ負の辺を経路として選択できるので最短経路が定まらない。
- 最短経路が存在する場合、始点に隣接している頂点のうち最低でも一つは最短経路に含まれる。
- そしてその最短経路に含まれる頂点に隣接している未探索な頂点のうち、最低でも一つは必ず最短経路に含まれる。
当たり前なことを言っているだけだけど、2 と 3 の二つの性質が単一始点最短経路問題を考えるときにとても大事なポイントだと思います。
ここから下では単一始点最短経路問題で使われるアルゴリズムを列挙していきます。
BFS
(幅優先探索)
かなりざっくり言うと、始点に近いものから順に一回ずつ（一度探索した頂点を二度訪れないように）探索していく手法。
重みがないグラフ、またはそう見なせるとき（各辺の重みが等しいとき）に使える。
始点の距離を0、各頂点の最短距離の初期状態をINFとして、始点に近いものから順に一回ずつ探索しながら各頂点の最短距離を更新していけば、2 と 3 の性質から最短経路が求まる。
辺の数を としたときに、時間計算量は
例題
めちゃめちゃ教育的で、とてもよい問題だと思う。
自分の提出
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
constexpr int INF = 1001001001;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int r, c, sy, sx, gy, gx;
cin >> r >> c >> sy >> sx >> gy >> gx;
--sy;
--sx;
--gy;
--gx;
vector<string> g(r);
for (int i = 0; i < r; i++) {
cin >> g[i];
}
queue<P> q;
q.push(P(sy, sx));
int d[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
d[i][j] = INF;
}
}
d[sy][sx] = 0;
while (!q.empty()) {
P v = q.front();
q.pop();
int y = v.first;
int x = v.second;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(g[ny][nx] == '.' && d[ny][nx] > d[y][x] + 1) {
d[ny][nx] = d[y][x] + 1;
q.push(P(ny, nx));
}
}
}
cout << d[gy][gx] << endl;
return 0;
}
ベルマンフォード法
フォードベルマン法と呼ばれたりもする。
DPの考案者であるリチャード・E・ベルマンと、レスター・フォード・ジュニアによって開発されたアルゴリズム。
重み付きグラフで使うことができ、また、負の閉路を検出できる。
手順
- 最短距離について、始点を0、各頂点の初期値を INF とし、以下の処理を繰り返す。
- 辺をひとつ選択して、その辺を from から to に辿ったときのコストを計算し、to に記録された最短距離より小さくなるなら計算したコストで更新する。
- 2 をすべての辺で行う。
- すべての辺を一巡して更新がなくなったら終了する。
負の閉路がない場合は 手順 4. までで良い。しかし負の閉路が存在しうる場合は無限に更新される可能性があるため繰り返し回数を考慮する必要がある。
冒頭で示した単一始点最短経路の 3 の性質から、最短経路が存在するなら、すべての辺を調べるという操作で更新される頂点のうち最低でも一つは最短距離になっていることがわかる。
よって、最短経路が存在するなら、最悪なケースでもすべての辺を調べるという操作は 回でよいとわかる。（ここで、 はグラフに含まれる頂点の数を示す。）
また、上記からすべての辺のトラバースを 回繰り返したときに最短距離の更新が止まるかどうかを調べれば負の閉路を検出できる。
すべての辺を調べるという操作の計算量は自明に なので、計算量は
例題
自分の提出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int v, e, r;
cin >> v >> e >> r;
vector<int> s(e, INF);
vector<int> t(e, INF);
vector<int> w(e, INF);
for (int i = 0; i < e; i++) {
cin >> s[i] >> t[i] >> w[i];
}
vector<vector<P>> adj(e);
for (int i = 0; i < e; i++) {
adj[s[i]].push_back(P(t[i], w[i]));
}
vector<int> d(v, INF);
d[r] = 0;
int cnt = 0;
while (cnt < v) {
bool updated = false;
for (int i = 0; i < e; i++) {
for (int j = 0; j < adj[i].size(); j++) {
int to = adj[i][j].first;
int cost = adj[i][j].second;
if (d[i] == INF) continue;
if (d[i] + cost < d[to]) {
d[to] = d[i] + cost;
updated = true;
}
}
}
if (!updated) {
break;
}
cnt++;
}
if (cnt == v) {
cout << "NEGATIVE CYCLE" << endl;
} else {
for (int i = 0; i < v; i++) {
if (d[i] < INF) {
cout << d[i] << endl;
} else {
cout << "INF" << endl;
}
}
}
return 0;
}
ダイクストラ法
重み付きグラフで使うことができるが、負の辺を含む場合は使えず、負の閉路の検出もできない。
一般にベルマンフォード法より高速なため、負の辺が含まれないとわかっている重み付きグラフではこちらがよく使われる。
最短経路が確定している小さな部分を考えた時に、その小さな部分を使ってさらに最短経路が確定している部分を広げていく、みたいな手法。
手順
- すべての頂点の最短距離の初期値を INF とする。
- 始点の最短距離を0とし、探索キューに追加、以下の処理を探索キューが空になるまで繰り返す。
- 探索キューの中でもっともコストが小さいものを取り出す。
- 取り出したものが既に探索済みな頂点の場合は破棄して 3. に戻る。
- この時点で、取り出した頂点への最短距離が取り出したコストで確定する。取り出した頂点から BFS の要領で隣接するすべての頂点を探す。
- 5. で探したすべての頂点へのコスト計算し、記録された最短距離より小さいなら記録を更新した上で探索キューに追加する。
負の辺がないため、手順 5. にて最短距離が確定するというところや、探索の深度を深める場合は最短距離が確定しているところから順にというところ、かつすでに最短距離が確定しているところを何回も無駄に調べたりしないといったところがポイント。
また、探索キューに優先度付きキュー（ヒープ）を使ったものとそうでない実装があるが、優先度付きキューを使ったほうが高速なため基本的にそちらを使う。
計算量は優先度付きキューを使った場合、手順 6. の処理は になる。そして 手順 6. は 最大で 回である。そして、手順 3. は 手順 6. より回数が増えることはないため計算量は
例題
自分の提出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;
constexpr int MAX_V = 200000;
struct Edge {
int to;
int cost;
};
// 隣接リスト
vector<Edge> g[MAX_V]; // g[i] := 頂点iから生えてる全ての辺のリスト
int d[MAX_V]; // 頂点d[v]への最短距離
void dijkstra(int s) {
d[s] = 0;
// firstを最短距離、secondを頂点番号
priority_queue<P, vector<P>, greater<P>> pq;
pq.push(P(d[s], s));
while (!pq.empty()) {
int v_cost = pq.top().first;
int v = pq.top().second;
pq.pop();
if (d[v] < v_cost) continue; // 確定済みな頂点は無視
for (int i = 0; i < g[v].size(); i++) {
int c = g[v][i].to;
int c_cost = g[v][i].cost; // 辺vcのコスト
int cost = v_cost + c_cost; // 頂点cへの合計コスト
if (d[c] > cost) { // すでに記録されてるものより低コストなら更新
d[c] = cost;
pq.push(P(cost, c));
}
}
}
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int V, E, r;
cin >> V >> E >> r;
fill(d, d + V, INF);
// 隣接リストの作成
for (int i = 0; i < E; i++) {
int s, t, cost;
cin >> s >> t >> cost;
Edge edge = {t, cost};
g[s].emplace_back(edge);
}
dijkstra(r);
for (int i = 0; i < V; i++) {
if (d[i] == INF) {
cout << "INF" << endl;
} else {
cout << d[i] << endl;
}
}
return 0;
}
おわり😇
