最短経路問題：ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法（6題）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本（通称：蟻本）の章末で紹介されている練習問題をひたすら解いている。今回は最短経路問題。はじめに最短経路問題を解くアルゴリズムの解説を読んだとき、わりと難しいなあという印象があった。が、練習問題を地道に解いていくと、アルゴリズムが自然だなあという感想になった。練習の力は偉大だ。

ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法のまとめ

最短経路を計算する三つのアルゴリズムをかなりざっくりまとめておく。動的計画法や貪欲法がわかってくると、これらのアルゴリズムがかなり自然な発想であることが見えてくる。状況の使い分けと計算時間は次のとおりである。
ダイクストラ法：単一始点最短経路問題（負の閉路がない場合）, O(E * logV)
ベルマンフォード法：単一始点最短経路問題（負の閉路がある場合）, O(V*E)
ワーシャルフロイド法：全点対最短経路問題, O(V^3)

ダイクストラ法

負の閉路を持たない単一始点最短経路問題に使える。つまり、辺のコストが0以上で、スタート地点（またはゴール地点）が決まっている場合に、グラフの各頂点への最短経路を計算することができる。

発想は、貪欲法である。
貪欲法は簡単にいうと、
「残っている要素の中から最も◯◯なもの選んでをxxする」
という言い方で表せるアルゴリズムである。

ダイクストラ法は、貪欲法っぽく表現すると、
「残っている頂点の中から、始点からの距離が最も小さいものを選んで、その頂点から1辺を通っていける頂点の距離を更新する」
となる。

d[i] = (始点から頂点iへの最短距離)

となるように意図する。簡単のため始点は頂点0としよう。初期化は d[0] = 0, d[i] = INF (i != 0) としておく。

はじめ、頂点0のから1辺を通っていける頂点の周りのd[i]の値を更新する。そして頂点0を「確定」する。
つぎに、未確定の頂点のうち、d[i]が最小のiをとって、頂点iから1辺を通っていける頂点jのd[j]をそれぞれ更新する。そして頂点iを確定する。
これを繰り返して、未確定の頂点がなくなるまでループ。

ループが終わったとき、各 d[i] は「始点から頂点iへの最短距離」を表している。

ベルマンフォード法

ダイクストラ法と同じく単一始点最短経路問題に有効だが、ベルマンフォード法は負の経路を持っていてもよい。ダイクストラ法が頂点に着目していたのに対し、ベルマンフォード法では辺に着目する。つまり、「辺についてのループ」である。

上と同じように、d[i]を定義する。初期化も同様。

d[i] = (始点から頂点iへの最短距離)

辺についてループしながらどのようにd[i]を更新していけば、最短距離が求まるだろうか。

辺を向き付けして、辺e、頂点i、頂点jが下のような関係だとしよう。
(頂点i) -----(辺e)------> (頂点j)
このとき、dが更新できそうな頂点はjである。
すでにそれまでに計算してあるd[j]よりも、 d[i] + (eのコスト) が小さければ、d[j]を更新できる。

if (d[j] > d[i] + (eのコスト))
  d[j] = d[i] + (eのコスト);

そして、この更新を何度も繰り返していくと、d[i]がすべて計算できる。

ワーシャルフロイド法

ワーシャルフロイド法はシンプルな三重ループのアルゴリズムであるが、計算時間が O(V^3) になるので、頂点が V <= 200 くらい少ないときにだけ使える。ワーシャルフロイド法は頂点についての動的計画法なので、動的計画法がわかってくると理解しやすい、と思う。

頂点iと頂点jを結ぶ最短距離を求めたい。

つまり、

d[i][j] = (頂点iと頂点jの最短距離)

である。

当たり前のことだが、重要な事実がある。頂点iと頂点jを結ぶ最短経路は、別の頂点kを通るか、通らないかのどちらかである。この事実について考えると、もしも頂点iと頂点jを結ぶ最短経路が頂点kを通るならつぎの等式が成立する。

d[i][j] == d[i][k] + d[k][j]

さて、この性質をうまく使えないものか。
動的計画法は、上のdの代わりに別の定義を使う。あらためて以下のように考える。

d[i][j][k] = (頂点0から頂点kまでだけを通ってよいときの、頂点iと頂点jの最短距離)

使える頂点についての動的計画法である。頂点k-1までの最短距離d[i][j][k-1]が計算できていれば、頂点kまでの最短距離d[i][j][k]は、つぎの二つの小さいほうである。
(頂点i) ------ (頂点k)を通らない ------ (頂点j)
(頂点i) ------ (頂点k)を通る ------ (頂点j)
漸化式はつぎのとおり。

d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1]);

あとは、配列を再利用しながらこれをループするだけでよい。

AOJ0189: Covenient Location

問題

Convenient Location | Aizu Online Judge

解法

全点対最短経路問題。
町の数が10以下なので、ワーシャルフロイドの計算時間O(V^3)で通る。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1000000;
const int N = 10;

int main() {
  int n;
  while (true) {
    cin >> n;
    if (!n) break;
    int dp[N][N];
    // 初期化
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        dp[i][j] = INF; // i=jは？
      }
    }
    int a, b, c;
    while (n--) {
      cin >> a >> b >> c;
      dp[a][b] = c;
      dp[b][a] = c;
    }
    // ワーシャルフロイド法
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          if (dp[i][j] > dp[i][k] + dp[k][j])
            dp[i][j] = dp[i][k] + dp[k][j];
        }
      }
    }
    // 町ごとに通勤時間の総和を計算
    int sum[N];
    for (int i = 0; i < N; i++) {
      sum[i] = 0;
      for (int j = 0; j < N; j++) {
        if (i != j && dp[i][j] != INF) {
          sum[i] += dp[i][j];
        }
      }
    }
    // 通勤時間が最小の町を求める
    int ans_i = 0;
    for (int i = 1; i < N; i++) {
      if (sum[i] < sum[ans_i] && sum[i] != 0)
        ans_i = i;
    }
    // 出力
    cout << ans_i << " " << sum[ans_i] << endl;
  }
}

POJ2139: Six Degrees of Cowvin Bacon

2139 -- Six Degrees of Cowvin Bacon

問題概要

N頭の牛がいて、映画の「共演距離」を考える。まず、自分自身との共演距離は0である。ひとつの映画で牛iと牛jが共演していたら、牛iと牛jの共演距離は1である。また、牛iと牛jがどの映画でも共演していないが、牛iと牛kがひとつの映画で共演していて、牛kと牛jが別の映画で共演していれば、共演距離は2である。共演距離3,4,...も同様に定める。
ほかの牛たちとの共演距離の平均が最小となる牛について、その平均を100倍した整数を出力せよ。
2 <= N <= 300
1 <= M <= 10000 (Mは映画の本数)

解法

ワーシャルフロイド法。N^3 = 27,000,000 なのでO(N^3)で間に合う。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1000000;
const int MAX_N = 300;

int main() {
  // 入力
  int N, M, i, j, k;
  cin >> N >> M;
  // dpの初期化
  int dp[MAX_N][MAX_N];
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      if (i == j) {
        dp[i][i] = 0;
      } else {
        dp[i][j] = INF;
      }
    }
  }
  // 共演距離1
  int movie[MAX_N];
  int cows;
  while (M--) {
    cin >> cows;
    for (i = 0; i < cows; i++) {
      cin >> movie[i];
    }
    for (i = 0; i < cows - 1; i++) {
      for (j = i + 1; j < cows; j++) {
        dp[movie[i] - 1][movie[j] - 1] = 1;
        dp[movie[j] - 1][movie[i] - 1] = 1;
      }
    }
  }
  // ワーシャルフロイド
  for (k = 0; k < N; k++) {
    for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
        if (dp[i][j] > dp[i][k] + dp[k][j])
          dp[i][j] = dp[i][k] + dp[k][j];
      }
    }
  }
  // 各牛について平均距離の計算
  float mean[MAX_N];
  for (i = 0; i < N; i++) {
    mean[i] = 0;
    for (j = 0; j < N; j++) {
      // cout << dp[i][j] << endl;
      mean[i] += dp[i][j];
    }
    mean[i] /= N - 1;
    mean[i] *= 100;
  }
  // 最小の平均を出力
  int ans = INF;
  for (i = 0; i < N; i++) {
    ans = min(ans, (int)mean[i]);
  }
  cout << ans << endl;
}

POJ3259: Wormholes

問題概要

3259 -- Wormholes
負の辺が存在するグラフで、負の閉路が存在するなら"YES"を、存在しないなら"NO"を出力させる問題。

解法

ベルマンフォード法。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
const int MAX_N = 500;
struct edge {int from, to, cost;};

int main() {
  // ifstream cin("../test.txt");
  int F, N, M, W;
  cin >> F;
  int d[MAX_N];
  while (F--) {
    vector<edge> es;
    cin >> N >> M >> W;
    fill(d, d + N, INF);
    d[0] = 0;
    // 辺の入力
    int f,t,c;
    for (int i = 0; i < M; i++) {
      cin >> f >> t >> c;
      edge p1 = {f-1, t-1, c};
      edge p2 = {t-1, f-1, c};
      es.push_back(p1);
      es.push_back(p2);
    }
    for (int i = 0; i < W; i++) {
      cin >> f >> t >> c;
      edge wh = {f-1, t-1, -c};
      es.push_back(wh);
    }
    // ベルマンフォード。辺についてのループ
    int m = es.size();
    while (true) {
      bool flag = false;
      for (int i = 0; i < m; i++) {
        edge e = es[i];
        if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
          d[e.to] = d[e.from] + e.cost;
          flag = true;
        }
      }
      if (!flag || d[0] < 0) break;
    }
    // 出力
    if (d[0] >= 0) {
      cout << "NO" << endl;
    } else {
      cout << "YES" << endl;
    }
  }
}

POJ3268: Silver Cow Party

問題概要

3268 -- Silver Cow Party
有向グラフの単一始点（と単一終点）最短経路問題。

解法

負の経路がないのでダイクストラ法で解ける。単一終点問題は辺の向きを逆にすれば単一始点問題に帰着できる。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int INF = 100000000;
const int MAX_N = 1000;
struct edge{int to, cost;};

int main() {
  int N, M, X;
  cin >> N >> M >> X;
  X--;
  // 行きと帰り
  vector<edge> path[2][MAX_N];
  int f, t, c;
  for (int i = 0; i < M; i++) {
    cin >> f >> t >> c;
    f--; t--;
    edge e1 = {t, c};
    edge e2 = {f, c};
    path[0][f].push_back(e1);
    path[1][t].push_back(e2);
  }

  // pairは(最短距離、頂点の番号)
  priority_queue<P, vector<P>, greater<P> > qu;

  // dの初期化
  int d[2][MAX_N];
  fill(d[0], d[0] + N, INF);
  fill(d[1], d[1] + N, INF);
  d[0][X] = 0; d[1][X] = 0;

  // 行きと帰りで2回ダイクストラ
  for (int i = 0; i < 2; i++) {
    qu.push(P(0, X));
    while (!qu.empty()) {
      P p = qu.top();
      qu.pop();
      int v = p.second;
      if (d[i][v] < p.first) continue;
      for (int j = 0; j < path[i][v].size(); j++) {
        edge e = path[i][v][j];
        if (d[i][e.to] > d[i][v] + e.cost) {
          d[i][e.to] = d[i][v] + e.cost;
          qu.push(P(d[i][e.to], e.to));
        }
      }
    }
  }

  // 行きと帰りの最大値を探す
  int res = d[0][0] + d[1][0];
  for (int i = 1; i < N; i++) {
    int sum = d[0][i] + d[1][i];
    if (i != X && sum > res)
      res = sum;
  }

  cout << res << endl;
}

AOJ2249: Road Construction

問題概要

Road Construction | Aizu Online Judge
N(1 <= N <= 10000)個の町がある。ひとつは首都である。町々をつなぐ道路を建設する計画があったが、コストがかかりすぎるので、最初の計画からいくつか道路を除外して、新たな道路建設計画を立てることにした。そのとき、次の条件を満たすようにしたい。
・どの2つの町も、それらをつなぐ経路が存在する。
・首都から各町への最短距離は最初の計画から変わらないようにする。
これらの条件を満たす計画のうち、コストが最小となる計画のコストを出力せよ。与えられる道路の情報はM(1 <= M <= 20000)個。道路の情報は、どの町とどの町をつなぐかだけでなく、距離とコストが与えられる。

解法

首都から各町への最短距離は、負の経路を持たない単一終点最短経路問題なので、ダイクストラ法でいける。最短経路が複数ある場合には、首都に向かっていく最初に進む辺にかかるコストが最小のものを選ぶ。町iからの最短経路の求め方は、d[i] = d[j] + cost[i][j]を満たす町jが、最短経路上にある町となる。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int INF = 100000000;
const int MAX_N = 10000;
struct edge{int to, dist, cost;};

int main() {
  while (true) {
    // 入力
    int N, M;
    cin >> N >> M;
    if (!(N | M)) break;
    vector<edge> roads[MAX_N];
    int u, v, t, c;
    while (M--) {
      cin >> u >> v >> t >> c;
      u--; v--;
      edge e1 = {v, t, c};
      edge e2 = {u, t, c};
      roads[u].push_back(e1);
      roads[v].push_back(e2);
    }

    int d[MAX_N];
    fill(d, d + N, INF);
    d[0] = 0;
    // P(最短距離、頂点)
    priority_queue<P, vector<P>, greater<P> > qu;
    qu.push(P(0,0));
    // ダイクストラ
    while (!qu.empty()) {
      P p = qu.top();
      qu.pop();
      int v = p.second;
      if (d[v] < p.first) continue;
      for (int i = 0; i < roads[v].size(); i++) {
        edge e = roads[v][i];
        if (d[e.to] > d[v] + e.dist) {
          d[e.to] = d[v] + e.dist;
          qu.push(P(d[e.to], e.to));
        }
      }
    }

    // コスト最小の経路を探して、コストの和の最小値を求める
    int min_total = 0;
    for (int v = 1 ; v < N; v++) {
      int min_cost = INF;
      for (int i = 0; i < roads[v].size(); i++) {
        edge e = roads[v][i];
        if (d[v] == d[e.to] + e.dist && e.cost < min_cost)
          min_cost = e.cost;
      }
      min_total += min_cost;
    }

    // 出力
    cout << min_total << endl;
  }
}

AOJ2200: Mr.Rito Post Office

Mr. Rito Post Office | Aizu Online Judge

解法

N <= 200 の全点対最短経路問題なので、基本はワーシャルフロイド法。しかし、海路がひと癖ある。海路を通って町iに来た場合、あとで再び海路を使うには町iからでなければならないという制約があるので、ちょっと考えなくてはいけない。

結論としては、ワーシャルフロイドと動的計画法を組み合わせることにする。

まず、任意の2つの町の最短距離を、陸路のみを使った場合と海路のみを使った場合でそれぞれ求めることにする。
つまり、次の二つを計算する。
>>|cpp|
dl[x][y] = (町xから町yに陸路のみを使って行く最短距離)
ds[x][y] = (町xから町yに海路のみを使って行く最短経路)
|

これらはワーシャルフロイドで求められる。この時点では、船がどこに置いてあるかは気にしなくて良い。町xから町yに陸路のみでは行けない場合や、海路のみでは行けない場合もあるので、そのときには dl[x][y] = INF、 ds[x][y] = INF などとする。

次に、i番目の集荷が終わった時点での最短距離を求めたい。

ところが、船がどこに泊めてあるかによって最短距離は変わってくるので、dpを次のように定義する。

dp[i][j] = (i番目の集荷までの最短距離。ただしi番目の集荷が終わった時点で船がjに泊まっている)

集荷にあたって、町xから町yへの移動方法は2通りある。陸路と海路の両方を使う場合と、陸路のみを使う場合である。
町x -> 陸路で港町kへ -> 海路で港町jへ -> 陸路で町yへ
町x -> 陸路で町yへ
このことを考慮して漸化式を作ると、次の通り。

s = z[i-1];
g = z[i];
dp[i][j] = min(
  dp[i-1][j] + dl[s][g],
  dp[i-1][k] + dl[s][k] + ds[k][j] + dl[j][g] の最小値 for k in 0..N
);

あとは素直に実装すればよい。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 10000000;
const int MAX_N = 200;
const int MAX_R = 1000;
//struct edge {int };

int main() {
  // ifstream cin("../test.txt");
  while (true) {
    int N, M;
    cin >> N >> M;
    if (!(N | M)) break;
    // dl, dsの初期化
    int dl[MAX_N][MAX_N]; // 陸路の最短距離
    int ds[MAX_N][MAX_N]; // 海路の最短距離
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (i == j) {
          dl[i][i] = 0;
          ds[i][i] = 0;
        } else {
          dl[i][j] = INF;
          ds[i][j] = INF;
        }
      }
    }
    int x, y, t;
    char sl;
    while (M--) {
      cin >> x >> y >> t >> sl;
      x--; y--;
      if (sl == 'L') {
        dl[x][y] = t;
        dl[y][x] = t;
      } else if (sl == 'S') {
        ds[x][y] = t;
        ds[y][x] = t;
      }
    }
    // ワーシャルフロイド
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]);
          ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);
        }
      }
    }
    // dp 初期化
    int dp[MAX_R][MAX_N];
    int z[MAX_R];
    int R;
    cin >> R;
    for (int i = 0; i < R; i++) {
      cin >> z[i];
      z[i]--;
    }
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < N; j++) {
        dp[i][j] = INF;
      }
    }
    dp[0][z[0]] = 0;
    for (int j = 0; j < N; j++) {
      dp[0][j] = ds[z[0]][j];
    }
    // dp 計算
    int s, g;
    for (int i = 1; i < R; i++) {
      for (int j = 0; j < N; j++) {
        s = z[i-1];
        g = z[i];
        // dp[i-1][k] + dl[s][k] + ds[k][j] + dl[j][g] の最小値
        int min_s = INF;
        for (int k = 0; k < N; k++) {
          if (INF > dp[i-1][k] + dl[s][k] + ds[k][j])
            min_s = min(min_s, dp[i-1][k] + dl[s][k] + ds[k][j]);
        }
        min_s += dl[j][g];
        dp[i][j] = min(dp[i-1][j] + dl[s][g], min_s);
      }
    }
    // 出力
    int ans = INF;
    for (int i = 0; i < N; i++) {
      ans = min(ans, dp[R-1][i]);
    }
    cout << ans << endl;
  }
}