Floyd求最短路
#算法
Floyd算法求最短路即为求图中i点到j点的最短路径，实质是使用dp不断更新（或者说是不断松弛）
C++代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210;
const int MAX = 1e9;
int d[N][N];
int main() {
int n, m, x, y, z;
cin >> n >> m;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (i != j)d[i][j] = MAX;//除了自己到自己，最短路径全部设为MAX，以便后续更新
while (m--) {
cin >> x >> y >> z;
if (z < d[x][y])d[x][y] = d[y][x] = z;//无向图，两边都要设置，可能有重边，取最小的
}
//Floyd求最短路算法核心dp
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//输出
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++)
cout << d[i][j] << ' ';
cout << endl;
}
return 0;
}