大家想一想，spfa是从bfs演化过来的，dijkstra是贪心思想，由此可见，这些“高级”的最短路算法都是有基础算法演化得来的。
而我今天要说的算法就是由基础的动态规划演化出来的最短路算法-floyd
还有用一到题来开启今天的内容：GF和猫咪的玩具
题意分析：有n个圆环，将两个圆环用力拉可以将这两个圆环之间的绳索拉直（当然是最短的路径，因为要把更长的路径拉直最短的路径
就会被扯断），如果有两条长度一样的路径，只会拉直其中一条，问抓住两个圆环用力拉最多能拉直多少绳索。抽象一下题意，就是有
一个图包括n个点和m个长度为1的连接点的边，问任意两点间的最短路径长度的最大值是多少。
思路解析：如果要做这道题，当然可以做n遍spfa或dijkstra，但是那样的话写起来会很费劲，所以，我要隆重推荐这个算任意两点间最
短路的神器：floyd！这个算法是从动态规划中演化出来的，所以就用dp四步走来讲一下这个最短路算法。
1.状态：dis[i][j]表示从i到j的最短路。
2.初值：dis[i][j]=INF,对于每条路A—>B，dis[A][B]=1;
3.转移：dis[i][j]=min(dis[i][j],dis[i][k],dis[k][j]){1<=i,j,k<=n};
4.答案：看是什么题了，比如这道题就是max(dis[i][j]){1<=i,j<=n}
最后看一下这种算法的时间复杂度：转移中枚举状态是n^2，而转移是所以整个的时间复杂度是O(n^3)，能通过这道题。
用途：一般用于稠密图任意点间的最短路计算。
所以代码就是这样的吗？
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
看起来没什么问题，但是一做发现答案完全不对啊，可是这不是完全按照四步走写出来的代码吗？的确是这样，但我们还忽略了一个问题，
那就是dp的先后顺序。必须要把前面的求完才能用前面的转移后面的，也就是说我们的dis[i][j]的含义还有一些问题，那就是没有规定它的
中转点k，也就是说dis[i][j]的真正含义是当枚举到k时，从i到j经历的中转点为1~k时i到j的最短路径长度。
所以真正的正确的floyd代码是这样的，如果还有不明白的看注释
int dis[NR][NR]; //dis[i][j]表示从考虑中转点到k（其中k是在循环里面的）时i到j的最短路径 for(int k=1;k<=n;k++)// 枚举中转点 for(int i=1;i<=n;i++)//枚举起点 for(int j=1;j<=n;j++)//枚举终点 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//状态转移方程 //转移方程成立的原因：如果从i绕到k之后再绕到j比直接i到j更短，当然要选择短的那一种
最后，上这道题的完整代码：
#include<bits/stdc++.h> using namespace std; const int NR=1e2+10; const int INF=0x3f3f3f3f; int n,m; int dis[NR][NR]; //dis[i][j]表示从考虑中转点到k（其中k是在循环里面的）时i到j的最短路径 int read()//这道题不能用快读read否则有东西读不进去 { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); memset(dis,0x3f,sizeof(dis));//dis初值 scanf("%d%d",&n,&m);//点数和边数 for(int i=1;i<=n;i++) dis[i][i]=0;//从自己到自己当然长度为0 for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y);//读入x到y有边， dis[x][y]=dis[y][x]=1;//从x到y和从y到x都有长度为1的边 } for(int k=1;k<=n;k++)// 枚举中转点 for(int i=1;i<=n;i++)//枚举起点 for(int j=1;j<=n;j++)//枚举终点 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//状态转移方程 //转移方程成立的原因：如果从i绕到k之后再绕到j比直接i到j更短，当然要选择短的那一种 int ans=0; for(int i=1;i<=n;i++)//统计答案时枚举起点 for(int j=i+1;j<=n;j++)//统计答案时枚举终点 if(dis[i][j]!=INF) ans=max(ans,dis[i][j]);//更新答案 printf("%d",ans);//输出答案 return 0; }
你以为floyd只能做多源最短路吗?如果这样你就错了，它还能做一种叫做传递闭包的题。
先搞清楚概念：传递闭包指给定若干个元素已经若干个关系，要求这种关系具有可传递性，即AξB，BξC，则AξC,例如>,<就是可传递的。
建立邻接矩阵d，其中dp[i][j]=1/0表示i与j有/没有关系，特别的d[i][i]始终为1，使用floyd来解决传递闭包类问题。
代码如下：
bool d[NR][NR];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) d[i][i]=1;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
d[x][y]=d[y][x]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]|=d[i][k]&d[k][j];
}
最后，给大家推荐一道传递闭包的题，那就是 POJ1094 Sorting It All Out
原文链接: https://www.cnblogs.com/chen-1/p/12574538.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/376868
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
