博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最短路 之 floyd 算法
阅读量:6364 次
发布时间:2019-06-23

本文共 934 字,大约阅读时间需要 3 分钟。

Floyd

在我认为这是最短路算法中最简单的一个,也是最low的一个。

所以我们组一位大佬给他起了一个新的名字,叫做超时!!!

(其实如果数据范围很小的话,这个算法还是蛮好用的!!)

这个算法比较简单,要不我们直接上代码?!

 

#include
#include
#include
#include
#include
#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算法不能解决带有“负权回路”(或者叫“负权环”)的图,因为带有“负权回路”的图没有最短路。

 

转载于:https://www.cnblogs.com/z360/p/6790139.html

你可能感兴趣的文章
iOS模型以及使用
查看>>
NSString 去除空格
查看>>
swift - 网络请求数据处理 - 协议处理
查看>>
[BZOJ1588]营业额统计(Splay)
查看>>
[BZOJ 4869][SHOI&SXOI2017]相逢是问候(扩展欧拉定理+线段树)
查看>>
2017-08-13
查看>>
条件语句优化面面观
查看>>
集成友盟微信登录没有回调
查看>>
在CentOS Linux系统上,添加新的端口,启用ssh服务
查看>>
dbcp数据库连接池简单使用
查看>>
leetcode-38-Count and Say
查看>>
从零开始写一个node爬虫(上)—— 数据采集篇
查看>>
java调用远程服务器shell脚本
查看>>
贪吃蛇
查看>>
aardio单行的edit控件响应回车按键消息
查看>>
UVA 221 Urban Elevations
查看>>
[windows] gcc编译器
查看>>
php导出excel不断刷新缓冲区的思路(转)
查看>>
Postgresql:prepared statement "S_1" already exists
查看>>
数学基础知识03——坐标系变换
查看>>