为什么Floyd算法中k必须放在最外层

https://www.zhihu.com/question/30955032 可以看下知乎这个问题。 我之前一直以为我明白了这个算法，结果发现自己只是会打模版而已，这个算法的实际是动态规划

这个解释的非常好啊，就是知乎上的最高票答案，你要知道他是从上一层k转移过来的所以当前的f[i][j]都应该是完成上一层动态规划的，如果k不是在最外层，那么f[i][j]就不是完成上一层动态规划的后的状态，有可能有的点没有经过k-1这个点的松弛。

我尝试了一下，开三维数组把k放在最内层，但有时会更新不完，如POJ 3660，我用了如下代码也A掉了，但正确的写法仍然是要把k放在最外层，注意注意

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
const int MAX_V = 110;
bool e[MAX_V][MAX_V][MAX_V];
int N,M;
void floyd(){
for(int l=1;l<=3;l++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
for(int k=1;k<=N;k++)
if(e[k-1][i][k] && e[k-1][k][j])
e[k][i][j] = true;
else
e[k][i][j] = e[k-1][i][j];
}
int main(void){
while(scanf("%d %d",&N,&M) != EOF){
int x,y;
memset(e,false,sizeof(e));
for(int i=1;i<=M;i++){
scanf("%d %d",&x,&y);
e[0][x][y] = true;
}
floyd();
//
for(int i=1;i<=N;i++){
//
for(int j=1;j<=N;j++){
//
printf("%d ",e[N][i][j]);
//
}
//
printf("n");
//
}
int res = 0;
for(int i=1;i<=N;i++){
int sum = 0;
for(int j=1;j<=N;j++){
if(i == j)
continue;
if(e[N][i][j] || e[N][j][i])
sum++;
}
if(sum == N-1)
res++;
}
printf("%dn",res);
}
return 0;
}

最后

以上就是唠叨手机为你收集整理的为什么Floyd算法中k必须放在最外层的全部内容，希望文章能够帮你解决为什么Floyd算法中k必须放在最外层所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。