单源最短路-dijkstra算法及其优化
2021/5/20 1:25:55
本文主要是介绍单源最短路-dijkstra算法及其优化,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
dijkstra算法及其优化
题目描述:给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边,边长为 z。
输出格式
输出一个整数,表示 1号点到 n 号点的最短距离。
如果路径不存在,则输出 −1。
数据范围
1≤n≤500 1≤m≤10^5 图中涉及边长均不超过10000。
输入样例:
3 3 2 1 4输出样例:
3
分析:鉴于n的数据规模比较小,可用朴素迪杰斯特拉算法(适用于稠密图)
算法时间复杂度O(n^2)
code:朴素dijkstra
算法
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 510; int g[N][N]; int dist[N]; bool st[N]; int n,m; int Dijkstra(){ memset(dist,0x3f,sizeof dist); dist[1] = 0; //迭代n次,每次找到一个点,用它来更新它的可达点到起点的距离。 for(int i=0;i<n;i++){ int t = -1; //总是选出当前最短路还没有确定的点中到起点最近的点,并用它来更新它的可达点到起点的距离。(这是迪杰斯特拉算法的核心思想--贪心) //下面是找到当前没有确定最短路的点里到起点距离最短的点。 for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||dist[j]<dist[t])) t = j; } st[t] = true; //更新可达点 for(int j=1;j<=n;j++) dist[j] = min(dist[j],dist[t] + g[t][j]); } if(dist[n]==0x3f3f3f3f) return -1; return dist[n]; } int main(){ scanf("%d%d",&n,&m); memset(g,0x3f,sizeof g); while(m--){ int x,y,z; scanf("%d%d%d",&x,&y,&z); g[x][y] = min(g[x][y],z); } int t = Dijkstra(); printf("%d\n",t); return 0; }
分析:同一题,如果n的数据规模增大至10^5
那么,对于这种稀疏图,可以采用堆优化策略的dijkstra
算法来求解
代码如下:
//堆优化版dijkstra算法。 #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 2e5 + 10; typedef pair<int,int> PII;//第一分量存的是距离,第二分量存的是点编号 int h[N],e[N],ne[N],w[N],idx;//w为边的权值 ,用邻接表来存储稀疏图 ,数据结构类似哈希map, //h存放的是图中所有结点(h中每个元素将会拉着'一条链',表示该点可达点), //e[i] 表示的是第i条边指向的结点, //ne[i] 表示的是第i条边的下一条边 //w[i] 表示的是第i跳变的权重, //idx为当前边的编号。 int dist[N];//dist[i] 表示第i个点到起点的距离 bool st[N];//判断第i个点到起点的距离的最短路是否已确定 int n,m; void add(int a,int b,int c){ e[idx] = b;//idx边所指点是b w[idx] = c;//idx边的权值是c ne[idx] = h[a];//下面两行表示将b插入到a的可达点链的最前面。 h[a] = idx++; } int Dijkstra(){ //思想与宽搜类似 memset(dist,0x3f,sizeof dist); //鉴于题意要求最短路,所以采用小根堆来维护每个点到起点的距离,这样堆顶总是最短的路径 //因为dijkstra算法是基于贪心的,所以总用堆顶结点(当前所有点中到起点距离最小的点)来更新堆顶可达点到起点的最短路。 priority_queue<PII,vector<PII>,greater<PII> > p; dist[1] = 0; p.push({0,1});//把起点信息入堆,起点到自己距离为0,所以插入的是{0,1}; while(p.size()){ //堆顶出堆 auto t = p.top(); p.pop(); //堆顶可扩展点入堆 int distance = t.first; int ver = t.second; //如果ver这个点已近确定了它到起点的最短路,那么可以continue,因为如果它已经确定,那么它的可达点到起点的最短路已经会被它更新, //所以,重复操作可以得以避免。 if(st[ver]) continue; for(int i=h[ver];i!=-1;i=ne[i]){ int j = e[i]; if(dist[j] > distance + w[i]){ dist[j] = distance + w[i]; //可扩展点入堆 p.push({dist[j] , j}); } } //ver及其拓展点的最短路信息被更新后就设置ver点的最短路已经确定。 st[ver] = true; } if(dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main(){ scanf("%d%d",&n,&m); memset(h,-1,sizeof h); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } int t = Dijkstra(); cout<<t<<endl; return 0; }
这篇关于单源最短路-dijkstra算法及其优化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南