はじめに
最短経路問題の解法をまとめました．
また，経路復元や経路の数え上げについても記載しています．
プログラミングコンテストチャレンジブック を参考書として使っています．
グラフとは
グラフは頂点の集合 $V$ と辺の集合 $E$ から構成されます．
辺は2つの頂点間を繋ぎ，コストという属性値を持ちます．コストは時間や距離として表現されます．
辺に向きがあるものを有向グラフ，向きがないものを無向グラフと呼びます．
下図は無向グラフの例です．
グラフの表現
グラフをプログラムで表現する方法として，隣接行列と隣接リストが挙げられます．
隣接行列
頂点 $i$ と頂点 $j$ が隣接しているか否かを $g_{ij}$ で表します．
隣接していれば $g_{ij} = 1$，隣接していなければ $g_{ij} = 0$ とします．
無向グラフでは $g_{ij} = g_{ji}$ が成り立ちます．
| $i \backslash j$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $0$ | $0$ | $0$ | $0$ |
| $1$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ |
| $2$ | $0$ | $1$ | $0$ | $1$ | $0$ | $0$ |
| $3$ | $0$ | $0$ | $1$ | $0$ | $1$ | $1$ |
| $4$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ |
| $5$ | $0$ | $0$ | $0$ | $1$ | $1$ | $0$ |
- メリット：2頂点に辺があるかを定数時間で判定できる
- デメリット：辺の数が少ない場合，無駄なメモリ消費が発生する
コストを保持する場合は，頂点 $i, j$ 間のコスト $c_{ij}$ を使って，
隣接していれば $g_{ij} = c_{ij}$，隣接していなければ $g_{ij} = \inf$ とします．
| $i \backslash j$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|---|---|---|---|---|---|---|
| $0$ | $\inf$ | $3$ | $\inf$ | $\inf$ | $\inf$ | $\inf$ |
| $1$ | $3$ | $\inf$ | $1$ | $\inf$ | $2$ | $\inf$ |
| $2$ | $\inf$ | $1$ | $\inf$ | $5$ | $\inf$ | $\inf$ |
| $3$ | $\inf$ | $\inf$ | $5$ | $\inf$ | $2$ | $5$ |
| $4$ | $\inf$ | $2$ | $\inf$ | $2$ | $\inf$ | $4$ |
| $5$ | $\inf$ | $\inf$ | $\inf$ | $5$ | $4$ | $\inf$ |
隣接リスト
頂点 $i$ に隣接している頂点をリストで保存します．
| 頂点 | 隣接する頂点のリスト |
|---|---|
| $0$ | $1$ |
| $1$ | $0,2,4$ |
| $2$ | $1,3$ |
| $3$ | $2,4,5$ |
| $4$ | $1,3,5$ |
| $5$ | $3,4$ |
- メリット：メモリ消費を抑えられる
- デメリット：2頂点間に辺があるかを判定するのにリストを走査する必要がある
隣接している頂点番号だけでなく，コストも同時に保持できます．
| 頂点 | (隣接する頂点,その頂点へのコスト)のリスト |
|---|---|
| $0$ | $(1,3)$ |
| $1$ | $(0,3), (2,1) ,(4,2)$ |
| $2$ | $(1,1), (3,5)$ |
| $3$ | $(2,5), (4,2), (5,5)$ |
| $4$ | $(1,2), (3,2), (5,4)$ |
| $5$ | $(3,5), (4,4)$ |
最短経路問題
グラフの始点から終点への経路の中で，コストの和が最小となるものを最短経路と呼びます．
最短経路問題を解く手法を3つ紹介します．
Bellman-Ford法
始点から他の全ての頂点への最短経路を求めることができます．
始点 $s$ から頂点 $i$ への最短距離を $d_{i}$，頂点 $i$ から頂点 $j$ へのコストを $c_{ij}$ とすると，以下の式が成り立ちます．
d_{i} = \min\left\{d_{j} + c_{ji} \mid e = (j, i) \in E\right\}
初期値を $d_{s} = 0$，$d_{i} = \inf$ として，上式を繰り返し適用することで最終的な結果を得ます．
負の閉路が存在しなければ，最短経路は同じ頂点を通らないため，繰り返し回数は最大 $|V| - 1$ 回になります．
一方，負の閉路が存在する場合は，その閉路を巡回することでいくらでもコストを小さくすることができます．
よって，$|V|$ 回目のループで更新が発生する場合は，負の閉路が存在することになります．
以下の擬似コードでは，最短経路問題を解きつつ，負の閉路があるか否かを判定しています．
struct edge {
int from;
int to;
int cost;
};
int V, E, d[MAX_V];
edge es[MAX_E];
bool has_negative_loop(int s) {
fill(d, d + V, INF);
d[s] = 0;
for (int i = 0; i < V; i++) {
for (int j = 0; j < E; j++) {
edge e = es[j];
if (d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
if (i == V - 1) {
return true;
}
}
}
}
return false;
}
Dijkstra法
負のコストの辺がない場合を考えます．
Dijkstra法は，最短距離が確定した頂点に隣接する頂点への距離を更新します．
負のコストの辺が存在しないので，更新した頂点の中でコストが最小のものの最短距離が確定します．
この確定した頂点を使って，さらに距離を更新していきます．
初期状態では，始点 $s$ の最短距離が $0$ で確定しています．
以下の擬似コードでは，コストが最小の頂点を取り出すのに priority_queue を使っています．
struct edge {
int to;
int cost;
};
typedef pair<int, int> P; // first: 最短距離, second: 頂点番号
int V, d[MAX_V];
vector<edge> G[MAX_V]; // 隣接リスト表現
void dijkstra(int s) {
fill(d, d + V, INF);
d[s] = 0; // 始点sへの最短距離は0
priority_queue<P, vector<P>, greater<P>> que; // 距離が小さい順に取り出せるようgreater<P>を指定
que.push(P(0, s));
while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second; // 更新した頂点の中で距離が最小の頂点v
if (d[v] < p.first) {
continue;
}
for (auto e : G[v]) { // 頂点vから出る辺eを走査
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
Warshall-Floyd法
すべての2頂点間の最短距離を求めることができます．
（Bellman-Ford法とDijkstra法は，始点からその他の頂点への最短距離を求める手法です．）
頂点 $0 \sim k$, $i$, $j$ を使う場合の $i$ から $j$ への最短距離を $d_{k, ij}$ とします．
以下2パターンに分解できます．
- 頂点 $k$ を通らずに $i$ から $j$ へ到達
- 頂点 $k$ を通って $i$ から $j$ へ到達
1.は頂点 $0 \sim k - 1$ のみを使って $i$ から $j$ へ到達する最短距離と一致するので $d_{k, ij} = d_{k-1, ij}$ になります．
2.は頂点 $0 \sim k - 1$ のみを使って $i$ から $k$ へ到達する最短距離と $k$ から $j$ へ到達最短距離の和になるので，
$d_{k, ij} = d_{k-1, ik} + d_{k-1, kj}$ になります．
よって，更新式は以下のようになります．
d_{k, ij} = \min\left\{d_{k-1, ij}, d_{k-1, ik} + d_{k-1, kj}\right\}
以下の擬似コードでは，同じ配列を使い回しています．
d_{ij} = \min\left\{d_{ij}, d_{ik} + d_{kj}\right\}
int d[MAX_V][MAX_V];
int V;
void warshall_floyd() {
for(int k = 0; k < V; k++) {
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
経路復元
コストを更新するときにその頂点の直前の頂点を保持します．
今回紹介したどの手法でも使える方法です．
struct edge {
int from;
int to;
int cost;
};
int V, E, d[MAX_V], prev[MAX_V];
edge es[MAX_E];
void bellman_ford(int s) {
fill(d, d + V, INF);
d[s] = 0;
fill(prev, prev + V, -1);
for (int i = 0; i < V; i++) {
for (int j = 0; j < E; j++) {
edge e = es[j];
if (d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
prev[e.to] = prev[e.from]; // 直前の頂点を保持
}
}
}
}
経路の数え上げ
最短距離となる経路の数を求める問題では，Dijkstra法に一手間加えます．
各頂点への最短経路数を保持する配列を用意し，コストを更新するif文の中で最短経路数も更新します．
struct edge {
int to;
int cost;
};
typedef pair<int, int> P; // first: 最短距離, second: 頂点番号
int V, d[MAX_V], cnt[MAX_V];
vector<edge> G[MAX_V]; // 隣接リスト表現
void dijkstra(int s) {
fill(d, d + V, INF);
d[s] = 0; // 始点sへの最短距離は0
fill(cnt, cnt + V, 0);
cnt[s] = 1; // 始点sへの最短経路数は1
priority_queue<P, vector<P>, greater<P>> que; // 距離が小さい順に取り出せるようgreater<P>を指定
que.push(P(0, s));
while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second; // 更新した頂点の中で距離が最小の頂点v
if (d[v] < p.first) {
continue;
}
for (auto e : G[v]) { // 頂点vから出る辺eを走査
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
cnt[e.to] = cnt[v]; // コストが更新された場合は直前の頂点への最短経路数で上書き
} else if (d[e.to] == d[v] + e.cost) {
cnt[e.to] += cnt[v]; // コストが一致する場合はこれまでの最短経路数を足し合わせ
}
}
}
}