Floyd算法通讲

批判一句

虽然我不知道为什么会有那么多的人在乱讲，但是我无能为力，只能尽量去讲述正确的思路

Floyd标程

Floyd算法，是一个基于dp而成的算法，因为是dp所以一定是从最优解到达最优解，所以网络上的那些什么经过k点转移过去的答案是不可靠的，因为每次转移过去的两个值并不是最优解，所以这样理解肯定是不对的。

因为是dp，我们可以将k定义成经过的点的编号不超过k，也就是说，我们的dp数组应该长成这样
$$dp[i][j][k]//从i到j的路径上的编号不超过k的最小值$$
如果是这样理解的话，我们转移的时候就有一下两种情况

那么我们就可以写出一下状态转移方程
$$dp[i][j][k]=dp[i][j][k-1]//如果当前这条路径上的点都小于k$$
$$dp[i][j][k]=dp[i][k][k-1]+dp[k][j][k-1]//因为有点k，所以以点k为分界点，将左右两边的最优解加起来$$
注意：这里的把看作为转换点和网络上的是不一样的，这里是有限制的。
所以我们把这两个状态转移方程合并一下就可以得到以下内容
$$dp[i][j][k]=min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1])$$
此时我们的边界条件是 $dp[i][j][0]=mp[i][j]$（不存在的边存为无无穷大）
可以发现，我们只做了一次dp，并且k的值是递增的，所以我们只需要开一个二维数组就行了，这里有点像滚动数组。

示范代码

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]);
}
}
}

最小环与Floyd

如果我们要在一个图中，找到一个至少有3个节点的环，那么我们可以怎么办呢？
考虑Floyd算法的过程，因为 $dis[i][j]$ 在外层循环的时候，是存储的“经过编号不超过 $k-1$ 的结点，从 $i$ 到 $j$ 的最短路的长度，因此我们就可以想到$min(dis[i][j]+a[j][k]+a[k][i])(1\le i<j<k)$就是满足以下两个条件的最小环的长度：

• 由编号不超过k的节点构成
• 经过了节点k

注：上述的$i,j$是枚举了与$k$相邻的两个点
这里有一个易错点，为什么是$dis[i][j]+a[j][k]+a[k][i]$而不是$dis[i][j]+dis[j][k]+dis[k][i]$？
客观的说，我刚开始也没搞懂，其实这里画个图就行了。

因为我们开的是滚动数组，所以我们需要在进行Floyd的同时，计算最小环，也就是说，我们要把计算最小的代码放在计算Floyd的前面，因为我需要用的是所经过的节点的编号不超过k-1的值，如果放在后面的话，就变成计算节点编号不超过k的值了。

示范代码

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e13;
long long a[310][310],dis[310][310];
long long n,m,ans=INF;
int main(){
cin>>n>>m;
memset(dis,0x3f3f,sizeof(dis));
memset(a,0x3f3f,sizeof(a));
for (int i=0;i<=n+5;i++){
a[i][i]=0;
dis[i][i]=0;
}
for (int i=1;i<=m;i++){
long long x,y,z;
cin>>x>>y>>z;
a[x][y]=a[y][x]=min(a[x][y],z);
dis[x][y]=dis[y][x]=a[x][y];
}
for (int k=1;k<=n;k++){
//计算最小环 
for (int i=1;i<k;i++){//因为是计算编号数小于等于k-1的结点，所以是i<k 
for (int j=i+1;j<k;j++){
ans=min(dis[i][j]+a[i][k]+a[k][j],ans);
}
}
//计算Floyd 
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]);
}
}
}
if (ans==INF)cout<<"No solution.";
else cout<<ans;
return 0;
}

原文地址：https://blog.csdn.net/CylMK/article/details/142762720

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！