2 次元グリッド上でダイクストラ法を使いたい話

お久しぶりです。
グリッド上でダイクストラ法を行うときに少し詰まったので備忘録も兼ねて書いておこうと思います。
ダイクストラ法を知っている前提で話が進むのでご容赦ください。。。

どんな問題に使えるのか

普通のダイクストラ法との違いは？

using P = pair<int, int>;
 
struct edge {
    int to;
    int cost;
};
 
vector<int> dist;
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<int, pair<int, int> > を使用している

です。

ちょっとしたプログラムの解説

各地点へのコストを表す配列が 2 次元なわけ
グリッド上では各地点が x 座標、y 座標の 2 点で表されます。
そのため dist[x][y] = cost で、ダイクストラの開始地点から座標 (x, y) へのコストを表しています。
priority_queue にどんな形の値を入れているか
第一引数に注目していただければわかるのですが、pair<int, pair<int, int> > の形で値が入っていきます。
2 つ目の pair<int, int> で座標 (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;
}

終わり

ここまでで記録しておきたかったことは終わりです。
もし何かの役に立てば幸いです。