Loading... 先引用一段度娘的话： > Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 为了求**任意两点间的最短路径**，可以把每个点当作起点，求每个点的单源最短路径问题。不过在这类问题中，图一般比较稠密。使用Floyd算法可以在$O(n^3)$的时间内完成求解，而且代码十分简单。（~~重点是简单！~~） 状态转移方程： $$ D[i][j]=\min(D[i][j],D[i][k]+D[k][j] $$ 怎么理解这个状态转移方程呢？ 我们用d数组当作邻接表保存输入。D[i]\[j]表示节点i到节点j的最短距离，不过计算之前D[i]\[j]显然不一定是节点i到节点j的最短距离。这时就叫弗洛伊德对在i和j之间的所有其他点进行一次“松弛”。何为“松弛”？  举例说明，在上面的图中，处理前d[1]\[3]=5，显然不是最短路径。经过$D[1][3]=\min(D[1][3],D[1][2]+D[2][3]$的处理后，d[1]\[3]被更优的d[1]\[2]+d[2]\[3]更新了。如果d[i]\[j]的最优路径上有两个或更多的节点，将会进行多次更新。 那就...上代码 ```cpp #include <bits/stdc++.h> using namespace std; int n, m, d[310][310]; int main(){ scanf("%d%d", &n, &m); //邻接矩阵 memset(d, 0x3f, sizeof(d)); for(int i = 1; i <= n; ++i) d[i][i] = 0; for(int i = 0; i < m; ++i){ int x, y, z; scanf("%d%d%d", &x, &y, &z); d[x][y] = min(d[x][y], z); } //Floyd求两点间最短路径 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){ printf("%d ", d[i][j]); } printf("\n"); } return 0; } ``` 另外，Floyd算法可以解决**传递闭包问题**。关于Floyd算法求最小环问题、求强连通分量等更多内容以后有空补充...（~~成功水文~~） © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
