ワーシャル・フロイド法

コード例

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

int main() {
  // 頂点数
  int n = 6;

  // 隣接行列を用意。全てINFで埋めておく
  int INF = 1000000000;
  vector<vector<int>> edge(n, vector<int>(n, INF));

  // 辺の登録。
  edge[0][1] = edge[1][0] = 9;
  edge[0][4] = edge[4][0] = 3;
  edge[0][5] = edge[5][0] = 4;
  edge[1][2] = edge[2][1] = 4;
  edge[1][5] = edge[5][1] = 3;
  edge[2][3] = edge[3][2] = 2;
  edge[3][4] = edge[4][3] = 5;
  edge[3][5] = edge[5][3] = 5;
  edge[4][5] = edge[5][4] = 2;

  // 移動元と移動先が同じ場合は距離を0にしておく
  for (int i = 0; i < n; i++) {
    edge[i][i] = 0;
  }

  // 外側のループ変数は経由点、
  // 中央のループ変数は移動元の点、
  // 内側のループ変数は移動先の点になる
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
      }
    }
  }

  cout << edge[0][3] << endl; // 頂点0から3までの最短距離
  cout << edge[4][2] << endl; // 頂点4から2までの最短距離
}

計算量

頂点 V の数だけ走査するループが 3 重にあるので計算量は $O(|V|^3)$ になる。

解説/アルゴリズム

ワーシャル・フロイド法は全頂点対間の最短距離を求めるアルゴリズム。