ワーシャルフロイド法

概要

$k \in V$として、すべての$i,j \in V$に対して、

• $i$から$j$への経路$p_{i,j}$を通るコスト$c_{i,j}$と
• $i$から$k$を経由して$j$へ向かう経路$p_{i,k,j}$を通るコスト$c_{i,k,j}$

の小さい方を$i$から$j$への経路のコストとして選択する。 これをすべての$k$について行うと、すべての$i,j\in V$に対する最短経路を得られる。

解釈

$k = n$のとき、$c_{i,j}$は$p_{i,j}$の道中に頂点${0, 1, ..., n-1, n}$のみを含むときの最短経路を表す。

コード

// V = {0, 1, ..., N - 1}のときのワーシャルフロイド法
Array2D<uint64_t> warshall_floyd(const Graph& graph) {
  const size_t N = graph.vertex_count();  // 頂点数
  Array2D<uint64_t> distances(N, N);  // NxNの2次元配列

  // 初期化
  for (size_t i = 0; i < N; ++i) {
    for (size_t j = 0; j < N; ++j) {
      if (i == j) {
        // 自分自身への距離は0になる
        distances[i][j] = 0;
      } else if (graph.has_edge(i, j)) {
        // グラフがiからjへの辺を持っていれば、その辺の重みを使う
        distances[i][j] = graph.edge(i, j);
      } else {
        // それ以外ならば、到達できないことを表す大きな値を使う
        distances[i][j] = UINT64_MAX;
      }
    }
  }

  // 最短経路を計算する
  for (size_t k = 0; k < N; ++k) {
    for (size_t i = 0; i < N; ++i) {
      for (size_t j = 0; j < N; ++j) {
        distances[i][j] = std::min(distances[i][j], distances[i][k] + distances[k][j]);
      }
    }
  }

  return distances;
}