戴尔官方网站建设启示,如何给网站做2维码,工业设计ai软件,crm管理系统开发语言适用情景Floyd算法适用于多源汇最短路#xff0c;也就是他问你比如说从3号点到6号点的最短路距离#xff0c;比如说从7号点到20号点的最短路距离#xff0c;而不是单源最短路#xff08;从1号点到n号点的最短路距离#xff09;。在这个算法当中允许负权边的存在。但在求最…适用情景Floyd算法适用于多源汇最短路也就是他问你比如说从3号点到6号点的最短路距离比如说从7号点到20号点的最短路距离而不是单源最短路从1号点到n号点的最短路距离。在这个算法当中允许负权边的存在。但在求最短路距离当中包括其他算法也一样是不能够出现负环的因为这样最短路距离可能变到负无穷去了时间复杂度三重无脑循环显然O(N^3)。算法解释首先对于Floyd算法来说对于图的存储必须要用邻接矩阵来存不能用邻接表。然后对于邻接矩阵一开始当然得初始化这边必须得注意由于是图这个矩阵无论是行还是列有效位都是从一开始。int dist[N][N]; //N表示图中点的个数1然后Floyd算法是允许这个图当中存在负权边但是不能出现负环因为在最短路问题当中的话一旦出现负环最短路可能变成负无穷。然后需要对dist数组初始化这边再提一句我们现在已经是默认图当中没有负环好那么现在如果说存在自环的话肯定是正的在最短路当中那就不予考虑于是在初始化的过程当中如果说i等于j直接就是0其他的话就初始化成正无穷为什么要正无穷想想就知道了等会儿我肯定需要min操作嘛for (int i1;in;i)
{for (int j1;jn;j){if (ij){dist[i][j]0;}else{dist[i][j]0x3f3f3f3f;}}
}然后当往这个邻接矩阵当中去输入一条一条图当中的边的时候由于我们现在是最短路问题因此我们只需要取小的就可以了然后如果是自环的话所以我们默认是没有负环的因此取小后就是0while(m--)
{scanf(%d %d %d,a,b,c);dist[a][b]MIN(dist[a][b],c);
}然后接下来就是执行Floyd算法其实就是三重循环外循环k从1到n第二层循环i从1到n第三层循环j从1到n。然后每一层循环的话就如下比较一下至于原理的话这个是与动态规划有关像我现在的话也掌握不了先把算法的步骤先记牢吧for (int k1;kn;k)
{for (int i1;in;i){for (int j1;jn;j){dist[i][j]MIN(dist[i][j],dist[i][k]dist[k][j]);}}
}然后当这三重循环结束之后原先dist数组是用来存边的现在他已经像孙悟空变身一样变成了从i到j的最短距离了。当然也有可能的情况就是从i到j的话是走不到的这时候还谈个屁最短路啊那如何去判断走不到的这种情况呢由于是允许存在负权边的情况因此当在更新的时候有可能会把这个无穷大的值稍微更新了小了一些因此不能直接dist[ i ][ j ] 等于 0x3f3f3f3fwhile(k--)
{scanf(%d %d,a,b);if(dist[a][b]0x3f3f3f3f/2){printf(impossible\n);}else{printf(%d\n,dist[a][b]);}
}例题来源AcWing854. Floyd求最短路 - AcWing题库#include stdio.h
#define N 210
#define MIN(a,b) ((a)(b)?(a):(b))
int dist[N][N];
int main()
{int n,m,k,a,b,c;scanf(%d %d %d,n,m,k);for (int i1;in;i){for (int j1;jn;j){if (ij){dist[i][j]0;}else{dist[i][j]0x3f3f3f3f;}}}while(m--){scanf(%d %d %d,a,b,c);dist[a][b]MIN(dist[a][b],c);}for (int k1;kn;k){for (int i1;in;i){for (int j1;jn;j){dist[i][j]MIN(dist[i][j],dist[i][k]dist[k][j]);}}}while(k--){scanf(%d %d,a,b);if(dist[a][b]0x3f3f3f3f/2){printf(impossible\n);}else{printf(%d\n,dist[a][b]);}}return 0;
}
