图论:Ford 算法 求最短路径
2022/5/10 17:00:31
本文主要是介绍图论:Ford 算法 求最短路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Ford 算法 求最短路径 先构建邻接表数组和初始化邻接关系int v1[maxn],v2[maxn],w[maxn];//记录起点终点和权值 for(int i=1;i<=m;++i) { cin>>u>>v>>val; v1[i]=u; v2[i]=v; w[i]=val; }
构建一维数组d,记录距离出发点的距离,d[出发点]初始化为0,自己和自己的距离为0,其他点和出发点的d先初始化为oo,并且构建pre数组,便于递归输出最短路径。出发点的前驱结点设为0,代表出发点没有前驱结点,也是一会递归输出路径的退出条件。
int d[maxn],pre[maxn];//记录距离出发点的距离 和最短路径的前驱结点 for(int i=0;i<=n;++i)d[i]=0x7fffff;//先初始化为oo 很大的值 d[s]=0;//自己到自己的距离为0; pre[s]=0;
核心算法代码就是一个二维数组,外层循环n-1次,内层循环m次,内层是循环m个邻接关系,每次更新d,外层循环n-1次,是刚好循环n-1次可以把所有点到起点的最短距离更新完。内层循环中,定义起点为u,终点为v,进行两个if判断,①:如果d[u]+边权<d[v]就更新d[v],就是更新v到起点的距离,②:如果d[v]+边权<d[u] 就更新起点到u的距离。注意两次更新中,如果有更新,都要改变pre数组,像第一次if 如果更新,就说明起点到u 再到 v的路径更短,所以 v的前驱是u 更新pre[v]=u,后面同理。
for(int i=1;i<=n-1;++i)//最多n-1次 for(int j=1;j<=m;++j) { u=v1[j],v=v2[j]; if(d[u]+w[j]<d[v]) { d[v]=d[u]+w[j]; pre[v]=u; } if(d[v]+w[j]<d[u]) { d[u]=d[v]+w[j]; pre[u]=v; } }
输出路径的递归函数:
void print(int i)//递归输出路径代码 { if(pre[i]) print(pre[i]); cout<<i<<" "; }
完整代码:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=100; int v1[maxn],v2[maxn],w[maxn];//记录起点终点和权值 int d[maxn],pre[maxn];//记录距离出发点的距离 和最短路径的前驱结点 int n,m,s;//n个结点 m条边 s为出发点 int u,v,val;//起点和终点 void print(int i)//递归输出路径代码 { if(pre[i]) print(pre[i]); cout<<i<<" "; } int main() { cin>>n>>m>>s; for(int i=0;i<=n;++i)d[i]=0x7fffff;//先初始化为oo 很大的值 for(int i=1;i<=m;++i) { cin>>u>>v>>val; v1[i]=u; v2[i]=v; w[i]=val; } d[s]=0;//自己到自己的距离为0; pre[s]=0; for(int i=1;i<=n-1;++i)//最多n-1次 for(int j=1;j<=m;++j) { u=v1[j],v=v2[j]; if(d[u]+w[j]<d[v]) { d[v]=d[u]+w[j]; pre[v]=u; } if(d[v]+w[j]<d[u]) { d[u]=d[v]+w[j]; pre[u]=v; } } for (int i = 1; i <= n; ++i) { cout << d[i] << endl; print(i); } return 0; }
这篇关于图论:Ford 算法 求最短路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?