首页 > 代码库 > 最短路 之 floyd 算法
最短路 之 floyd 算法
Floyd
在我认为这是最短路算法中最简单的一个，也是最low的一个。
所以我们组一位大佬给他起了一个新的名字，叫做超时！！！
（其实如果数据范围很小的话，这个算法还是蛮好用的！！）
这个算法比较简单，要不我们直接上代码？！
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define maxn 1000+15#define oo 123456using namespace std;int dis[maxn][maxn];int main(){ int x,y,z,n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=oo*(i!=j) ;//除了该点到他本身外其余的点其余的点全付成极大值 for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); dis[x][y]=z;//输入两城市间的和距离 } 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]); printf("%d",dis[1][n]);//输出从1到n的最短路 return 0;}
另外需要注意的是：Floyd-Warshall算法不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路。
最短路 之 floyd 算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。