首页 > 代码库 > 用小根堆实现dijkstra,求图的单源最短路径
用小根堆实现dijkstra,求图的单源最短路径
小根堆实现dijkstra
求图的最短路径,最常用的有四种方法:
1.Floyed(弗洛伊德)算法。最简单的最短路径算法,可以求多源最短路径。时间复杂度为O(n*n*n)。
2.Dijkstra(迪杰斯特拉)算法。只能求单源最短路径。时间复杂度为O(n*n)。
3.Bellman-Ford(贝尔曼福德)算法。只能求单源最短路径。时间复杂度为O(NE)(N为顶点数,E是边数)。
4.SPFA算法。为Bellman-Ford算法的队列实现,减少不必要的冗杂计算。只能求单源最短路径。时间复杂度为O(kE)(k是常数,平均值为2)。
由以上算法可知求单源最短路径,SPFA一般情况为耗时最少的。
但我们也使用Dijkstra算法。但它的时间复杂度也太高,于是我们就用小根堆优化Dijkstra,减少冗杂操作,达到减少时间的目的。
最好使用STL的优先队列来模拟小根堆,由于STL中的优先队列自动设为大根堆,所以我们把队列里的每个量都乘以-1,达到目的。
以下为代码实现:
1 #include<cstdio> 2 #include<queue> 3 #define N 420000 4 using namespace std; 5 priority_queue<int>s;//优先队列 6 int num_edge,head[N],a,b,c,d[N],n,m,x,y,p[N]; 7 struct hehe{ 8 int next; 9 int to; 10 int dis; 11 }edge[N]; 12 void add_edge(int from,int to,int dis){ 13 edge[++num_edge].next=head[from]; 14 edge[num_edge].to=to; 15 edge[num_edge].dis=dis; 16 head[from]=num_edge; 17 } 18 void dijkstra(){ 19 s.push(-a);//由于优先队列自动设为大根堆,所以可以把其中所有量都乘以-1,达到使用小根堆的要求 20 for(int i=1;i<=n;++i) 21 d[i]=4200000; 22 d[a]=0; 23 while(!s.empty()){ 24 x=s.top();//取出队首元素 25 p[-x]=1; 26 s.pop();//删除队首元素 27 for(int i=head[-x];i;i=edge[i].next){ 28 y=edge[i].to; 29 if(p[y]==1) 30 continue; 31 if (d[y]>d[-x]+edge[i].dis){ 32 d[y]=d[-x]+edge[i].dis; 33 if(!p[y]) 34 s.push(-y);//加入一个遍历元素 35 } 36 } 37 } 38 } 39 int main(){ 40 scanf("%d%d",&n,&m); 41 for(int i=1;i<=m;++i){ 42 scanf("%d%d%d",&a,&b,&c); 43 add_edge(a,b,c); 44 add_edge(b,a,c); 45 } 46 scanf("%d%d",&a,&b);//求a到b的最短路径 47 dijkstra(); 48 printf("%d",d[b]); 49 return 0; 50 }
用小根堆实现dijkstra,求图的单源最短路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。