最短路径算法——Floyd算法
2025-01-05 11:25:37
发布于：广东
2阅读
0回复
0点赞
| 名称 | 解决问题 |
|---|---|
| Bellman-Fold | 单源最短路径 |
| 迪杰斯特拉 | 稠密图 |
| Floyd | 多源最短路径 |
核心思路：
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]);//松弛操作
}
}
}
k是中转站，看一下a[i][j]是否小于dis[i][k]+dis[k][j]，如果大于，a[i][j]赋值为dis[i][k]+dis[k][j]，否则不变
运用Floyd算法需要用到邻接矩阵（无向图）
1.定义变量：邻接矩阵a,顶点个数n,边数m
int a[110][110],n,m;
2.输入顶点个数和边数，把邻接矩阵初始化无穷大，因为自己到自己不用走，所以代码为：
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) a[i][j]=0;//自己到自己不用走，赋值为0
else a[i][j]=1e9+10;
}
}
3.输出边数的起点，终点，权值
for(int i=1;i<=m;i++){
int start,end,val;
cin>>start>>end>>val;
a[start][end]=a[end][start]=val;
}
4.核心代码，实现Floyd算法
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]);//松弛操作
}
}
}
这里空空如也
有帮助，赞一个