Floyd为什么k循环要在最外层

本文主要是介绍Floyd为什么k循环要在最外层，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

适用情况：
该算法不能解决带有“负权回路”（或者叫“负权环”）的图

时间复杂度为 o(n^3)

参考博客：
作者：Yuliang.wang
地址：https://www.cnblogs.com/wangyuliang/p/9216365.html

代码

#include <bits/stdc++.h>
using namespace std;
int f[1020][1020];
int main(){int n,m,s,t;int x,y,z;cin >> n >> m >> s >> t;memset(f,0x3f,sizeof(f));for(int i = 0;i < m;i++){cin >> x >> y >> z;f[x][y] = min(f[x][y],z);//可能每对点有多条边f[y][x] = min(f[y][x],z);}for(int i = 1;i <= n;i++){f[i][i] = 0;}for(int k = 1;k <= n;k++){for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){//if(i != j && j != k && i!= k)f[i][j] = min(f[i][j],f[i][k] + f[k][j]);//f[i][k]+f[k][j]越界，所以f[][]不能赋值为127}}}if(f[s][t] >= 0x3f3f3f){cout << -1 << endl;}else cout << f[s][t] << endl;return 0;
}

注意
循环k要在最外层
如果写成内层，例如像下面一样是不行的

for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){for(int k = 1;k <= n;k++){f[i][j] = min(f[i][j],f[i][k] + f[k][j]);}	}}

因为floyd本质目的是对于每个点对i-j的距离可以被其它点优化，而且可以被多个点共同优化，如果循环k在内层，那么i,j每次只能得到一个点的优化。

如下列情况

如图

注意:初始时，两点间的路径还没被优化，所以只有两点直接有边才算有路径。

当算法跑到 i= 1，j = 2; k = 4;时

k循环在内部：
点1-2的路径只能通过单一的点，要么3（3-2路径还没被优化，所以没有路），要么4（1-4路径还没被优化，所以没有路）来优化路径，没有考虑到同时使用3，4来优化，于本意相反

k循环在最外部：
先用 k = 3优化 使得i->j->k :1->3->4 这样点对1-4就有路径了
k = 4 时 就可以得到 1->4->2; (1->4已经通过3优化了，相当于3也优化了1->2)，所以点对1-2的路径可以被3，4共同优化

算法思想：
folyd利用了动态规划的思想，学过背包问题的，不难发现，它和01背包很像，外围那个K循环就相当于物品，所以对每个点对i-j的路径，都可以选择1个、2个、……k个点对路径进行优化

这篇关于Floyd为什么k循环要在最外层的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---