C++ ワーシャルフロイド法

参考：素人によるワーシャルフロイド法 - Qiita

グラフ

コード

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
const int INF = 1e9;

void warshall_floyd(Graph &G) {
  int n = G.size();
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
      }
    }
  }
}

int main() {
  Graph G = {
      {0, 10, INF, 20, INF, INF, INF, 30},   // A (0)
      {10, 0, 10, INF, INF, INF, INF, INF},  // B (1)
      {INF, 10, 0, INF, 20, INF, INF, INF},  // C (2)
      {20, INF, INF, 0, INF, 20, INF, INF},  // D (3)
      {INF, INF, 20, INF, 0, INF, INF, 20},  // E (4)
      {INF, INF, INF, 20, INF, 0, 10, INF},  // F (5)
      {INF, INF, INF, INF, INF, 10, 0, 10},  // G (6)
      {30, INF, INF, INF, 20, INF, 10, 0}    // H (7)
  };
  warshall_floyd(G);
  for (vector<int> costs : G) {
    for (int cost : costs) {
      printf("%2d ", cost);
    }
    cout << endl;
  }
}

結果

 0 10 20 20 40 40 40 30 
10  0 10 30 30 50 50 40
20 10  0 40 20 60 50 40
20 30 40  0 60 20 30 40
40 30 20 60  0 40 30 20
40 50 60 20 40  0 10 20
40 50 50 30 30 10  0 10
30 40 40 40 20 20 10  0