ウォーシャル・フロイド法 - プログラミング道場 ACM/ICPC

ウォーシャル・フロイド法

隣接行列 d における各2点間の最短距離を求める。
i から j へ移動する際に、k を経由したほうが近い場合は更新する。

for (int k = 1; k < n + 1; k++)
  for (int i = 1; i < n + 1; i++)
    for (int j = 1; j < n + 1; j++)
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);