ABC 079 D - Wall - BEN2のブログ

ABC 079 D - Wall に関連する、ワーシャルフロイドについてのメモを残します。

参考

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者:渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 発売日: 2015/01/30
- メディア: 単行本（ソフトカバー）

わからん

ワーシャルフロイドの実装は数行で済むが、どうしてそのコードで最短距離を求められるのか。
この記事では、確かに最短距離を求められそうだな、と納得できることを目標とする。
具体例として、下に示すグラフについて全点対間最短経路問題を考えてみる。
便宜上、丸の中の数字は、頂点番号を表すことにする。 f:id:BEN2suzuka:20191103205631p:plain ソースコードは以下の通り。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int INF = 1000000000;
  // A[i, j] := 最終的には始点 i と終点 j の最短経路の距離
  // 初期値は、始点 i と終点 j を結ぶ辺の重み (長さ)
  // 始点 i と終点 j を結ぶ辺がない場合は INF
  vector<vector<int>> A = {
    { 0, 5, 100, INF, INF },
    { 5, 0, INF, 5, 50 },
    { 100, INF, 0, INF, 10 },
    { INF, 5, INF, 0, 5 },
    { INF, 50, 10, 5, 0 }
  };
  // ワーシャルフロイド
  // 始点を i、終点を j とする。k は経由する頂点
  for (int k = 0; k < 5; k++) {
    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
      }
    }
  }
  // 出力
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      cout << i << " -> " << j << " : " << A[i][j] << endl;
    }
  }
}

$k = 0$

上記ソースコードの $k$ のループを追いかけてみる。
$k = 0$ のループでは、始点が $i$ 、終点が $j$ の経路について、

$A [ i, j ]$ (0 を経由しない)
$A [ i, 0 ] + A [ 0, j ]$ (0 を経由する)

このうち小さい方を新たに $A [ i, j ]$ の値とする。
前者は $i$ → $j$ 、後者は $i$ → 0 → $j$ という経路である。 $x$ → $y$ と表記するとき、 $x$ から $y$ へ向かう途中に経由した頂点はないものとする。 f:id:BEN2suzuka:20191103164658p:plain たとえば、始点が 1、終点が 2 の経路ならば、

$A [ 1, 2 ] = \rm{INF}$ (0 を経由しない、1 → 2 という経路)
$A [ 1, 0 ] + A [ 0, 2 ] = 5 + 100 = 105$ (0 を経由する、1 → 0 → 2 という経路)

この 2 経路を比べ、小さい方である 105 を $A [ 1, 2 ]$ の値とする。 f:id:BEN2suzuka:20191104102518p:plain $k = 0$ 後の $A [ i, j ]$ は、始点 $i$ 、終点 $j$ の最短経路の距離を表している。ただし、端点である $i, j$ 以外に経由してよい頂点は 0 のみである。
遡ると、 $k = 0$ 前の $A [ i, j ]$ も始点 $i$ 、終点 $j$ の最短経路の距離を表すが、やはり制約付きで、端点である $i, j$ 以外に経由してよい頂点はない。

$k = 1$ 以降

$k = 1$ のループでは、始点が $i$ 、終点が $j$ の経路について、

$A [ i, j ]$ (1 を経由しない)
$A [ i, 1 ] + A [ 1, j ]$ (1 を経由する)

このうち小さい方を新たに $A [ i, j ]$ の値とする。
各部分路は 0 を経由するかどうかで 2 通り考えられるが、すでに $k = 0$ のループで最適な経路が選択されている。 f:id:BEN2suzuka:20191103164706p:plain たとえば、始点が 3、終点が 2 の経路ならば、

$A [ 3, 2 ] = \rm{INF}$ (1 を経由しない)
$A [ 3, 1 ] + A [ 1, 2 ] = 5 + 105 = 110$ (1 を経由する)

このうち小さい方である 110 を $A [ 3, 2 ]$ の値とすればよい。
ここで $A [ 3, 1 ]$ 、 $A [ 1, 2 ]$ は以下の通り、 $k = 0$ のループで、経由できる頂点は 0 のみの制約の下で最適な経路が選択されている。

始点が 3、終点が 1 の経路は、0 を経由しない方が距離は短い (3 → 1)
始点が 1、終点が 2 の経路は、0 を経由した方が距離は短い (1 → 0 → 2)

f:id:BEN2suzuka:20191106155200p:plain 以降、経由してよい頂点を 1 個増やすごとに最短経路の距離を更新していく。
下の表は、各ループ後の頂点間の距離を表し、 $k = 4$ 後の列が全点対間最短経路問題の答えとなる。 f:id:BEN2suzuka:20191103164649p:plain

一般化

頂点 0, 1, 2, ..., $k$ のみ経由できるとき、始点 $i$ 、終点 $j$ の最短経路の距離を $A^{k} [ i, j ]$ とし、その経路の 1 つを $P^{k} [ i, j ]$ とする。
ここで、 $A^{k-1} [ i, j ]$ を利用して $A^{k} [ i, j ]$ を求めることを考える。
始点が $i$ 、終点が $j$ の経路について、

$k$ を経由しないとき、頂点 0, 1, 2, ..., $k-1$ のみ経由できるので、最短経路は $P^{k-1} [ i, j ]$ と等しく、 $A^{k} [ i, j ] = A^{k-1} [ i, j ]$
$k$ を経由するとき、最短経路は $P^{k-1} [ i, k ]$ と $P^{k-1} [ k, j ]$ の 2 つの部分路から構成され、 $A^{k} [ i, j ] = A^{k-1} [ i, k ] + A^{k-1} [ k, j ]$

この 2 経路を比べ、小さい方を $A^{k} [ i, j ]$ の値とすればよい。
このように、 $A^{k-1} [ i, j ]$ により $A^{k} [ i, j ]$ が決定されることがわかる。
初期値を $A^{-1} [ i, j ]$ とすると、確かに $k = 0$ のループでは $A^{-1} [ i, j ]$ をもとに $A^{0} [ i, j ]$ を求め、 $k = 1$ のループでは $A^{0} [ i, j ]$ をもとに $A^{1} [ i, j ]$ を求めていた。 f:id:BEN2suzuka:20191103164716p:plain モヤモヤするのは、 $A^{-1} [ i, j ], \, A^{0} [ i, j ], \, A^{1} [ i, j ], \, \cdots$ のように、最短経路の距離の保持には 3 次元配列 $A [ i, j, k ]$ が必要と思うが、上記ソースコードでは 2 次元配列 $A [ i, j ]$ で実装している点。なぜ問題ないのか。

2 次元で足りる

上記ソースコードについて検討する。
同じ $k$ のループ内において、 $A^{k} [ 0, 0 ]$ が最初で $A^{k} [ 4, 4 ]$ が最後に計算されていた。
たとえば $A^{1} [ 3, 2 ]$ を求めるときは、

$A^{0} [ 3, 2 ]$ (1 を経由しない)
$A^{0} [ 3, 1 ] + A^{0} [ 1, 2 ]$ (1 を経由する)

この 2 つを比べるとよいが、これよりも前に $A^{1} [ 3, 1 ]$ や $A^{1} [ 1, 2 ]$ を求める計算は終わっていて、すでに $A^{0} [ 3, 1 ]$ 、 $A^{0} [ 1, 2 ]$ は上書きされてしまっている。
このように、 $A^{k} [ i, j ]$ を求めるとき、 $A^{k-1} [ i, k ]$ や $A^{k-1} [ k, j ]$ がすでに $A^{k} [ i, k ]$ 、 $A^{k} [ k, j ]$ に上書きされていることはありうる。
上書きされていては $A^{k} [ i, j ]$ を求めることができないのではないか、とモヤモヤする。
しかし、

$A^{k} [ i, k ]$ $= min( A^{k-1} [ i, k ], \, A^{k-1} [ i, k ] + A^{k-1} [ k, k ] )$ $= A^{k-1} [ i, k ]$
$A^{k} [ k, j ]$ $= min( A^{k-1} [ k, j ], \, A^{k-1} [ k, k ] + A^{k-1} [ k, j ] )$ $= A^{k-1} [ k, j ]$

であるため、上書きされることには実は問題がないことがわかる。
そのため、最短経路の距離の保持には 2 次元配列 $A [ i, j ]$ で足りる。

ABC 079 D - Wall

問題 : D - Wall

数字 $i$ $( 0 \leq i \leq 9 )$ を数字 $j$ $( 0 \leq j \leq 9 )$ に変えるのに必要な魔力が与えられる。数字 $i$ を 1 に変えるのに必要な魔力をワーシャルフロイド法により求める。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int H, W; cin >> H >> W;
  vector<vector<int>> c(10, vector<int>(10));
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) cin >> c[i][j];
  }
  vector<vector<int>> A(H, vector<int>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) cin >> A[i][j];
  }
  for (int k = 0; k < 10; k++) {
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (A[i][j] != -1) ans += c[A[i][j]][1];
    }
  }
  cout << ans << endl;
}