グリッド上でのダイクストラ法について自分が詰まってしまったので誰かの役に立てばと思い載せておきます。
どんな問題に使えるのか
普通のダイクストラ法との違いは？
using P = pair<int, int>;
struct edge {
int to;
int cost;
};
vector<int> dist;
vector<vector<edge> > g;
void dijkstra(int s) {
dist = vector<int>(n, Inf);
dist[s] = 0;
priority_queue<P, vector<P>, greater<P> > pq;
pq.push(P(0, s));
while (!pq.empty()) {
P p = pq.top();
pq.pop();
int v = p.second;
if (dist[v] < p.first) continue;
rep (i, g[v].size()) {
edge e = g[v][i];
if (dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
pq.push(P(dist[e.to], e.to));
}
}
}
}
これが自分が普段使っているダイクストラのコードです。
using P = pair<int, int>;
using PP = pair<int, P>;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<vector<int> > g, dist;
void dijkstra(int sx, int sy) {
dist = vector<vector<int> >(h, vector<int>(w, Inf));
dist[sx][sy] = 0;
priority_queue<PP, vector<PP>, greater<PP> > pq;
pq.push(PP(0, P(sx, sy)));
while (!pq.empty()) {
PP p = pq.top();
pq.pop();
int c = p.first;
int vx = p.second.first, vy = p.second.second;
rep (i, 4) {
int nx, ny;
nx = vx + dx[i], ny = vy + dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (dist[nx][ny] <= g[nx][ny] + c) continue;
dist[nx][ny] = g[nx][ny] + c;
pq.push(PP(dist[nx][ny], P(nx, ny)));
}
}
}
そしてこれが PAST の J 問題で使った グリッド上でのダイクストラのコードです。
大きな違いとしては
- struct edge を使うよりも 2 次元配列としてグラフを持つ方が楽
- 各地点へのコストを表す配列 (上記のコードでは dist) が 1 次元から 2 次元に変わっていること
- pairのネスト構造を使用している
です。
ちょっとしたプログラムの解説
-
各地点へのコストを表す配列が 2 次元なわけ
グリッド上では各地点が x 座標、y 座標の 2 点で表されます。
そのため dist[x][y] = cost で、ダイクストラの開始地点から座標 (x, y) へのコストを表しています。
-
priority_queue にどんな形の値を入れているか
第一引数に注目していただければわかるのですが、pair のネスト形で値が入っていきます。
2 つ目の pair で座標 (x, y) を、1 つ目の int に座標 (x, y) へのコストを入れています。
グリッド上ダイクストラでの経路復元
もちろん経路復元もできます。
using P = pair<int, int>;
struct edge {
int to;
int cost;
};
vector<int> dist, pre;
vector<edge> g;
void dijkstra(int s) {
pre = vector<int>(n, -1);
dist = vector<int>(n, Inf);
dist[s] = 0;
priority_queue<P, vector<P>, greater<P> > pq;
pq.push(P(0, s));
while (!pq.empty()) {
P p = pq.top();
pq.pop();
int v = p.second;
if (dist[v] < p.first) continue;
rep (i, g[v].size()) {
edge e = g[v][i];
if (dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
pq.push(P(dist[e.to], e.to));
}
}
}
}
vector<int> restore(int t) {
vector<int> path;
for (; t != -1; t = pre[t]) path.push_back(t);
reverser(path.begin(), path.end());
return path;
}
この普段のダイクストラでの経路復元に対し、
using P = pair<int, int>;
using PP = pair<int, P>;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<vector<int> > g, dist;
vector<vector<P> > pre;
void dijkstra(int sx, int sy) {
dist = vector<vector<int> >(h, vector<int>(w, Inf));
pre = vector<vector<P> >(h, vector<P>(w, P(-1, -1)));
dist[sx][sy] = 0;
priority_queue<PP, vector<PP>, greater<PP> > pq;
pq.push(PP(0, P(sx, sy)));
while (!pq.empty()) {
PP p = pq.top();
pq.pop();
int c = p.first;
int vx = p.second.first, vy = p.second.second;
rep (i, 4) {
int nx, ny;
nx = vx + dx[i], ny = vy + dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (dist[nx][ny] <= g[nx][ny] + c) continue;
dist[nx][ny] = g[nx][ny] + c;
pre[nx][ny] = P(vx, vy);
pq.push(PP(dist[nx][ny], P(nx, ny)));
}
}
}
vector<P> restore(int tx, int ty) {
vector<P> path;
int x, y;
for (; tx != -1 || ty != -1; tx = pre[x][y].first, ty = pre[x][y].second) {
path.push_back(P(tx, ty));
x = tx, y = ty;
}
reverse(path.begin(), path.end());
return path;
}
というようになります。
基本的には通常ダイクストラの応用ですが、for 文の変化式 (3つ目) で、以下のように書いてしまうとバグります。
(更新された tx の値が ty の値の取得に使用されてしまうため)
vector<P> restore(int tx, int ty) {
vector<P> path;
for (; tx != -1 || ty != -1; tx = pre[tx][ty].first, ty = pre[tx][ty].second) {
path.push_back(P(tx, ty));
}
reverse(path.begin(), path.end());
return path;
}
終わり
ここまでで記録しておきたかったことは終わりです。
もし何かの役に立てば幸いです。