dijkstra算法+堆优化 + 链式前向星版本
2021/7/27 17:35:40
本文主要是介绍dijkstra算法+堆优化 + 链式前向星版本,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
dijkstra算法+堆优化 + 链式前向星版本
堆优化版本结构简述
typedef pair一下 PII 邻接矩阵、邻接表或链式前向星add一下来建图 void dijkstra(int s){ 小根堆走起 给dist数组都赋值为无穷大(memset一下), 让起点拥有一个表现的机会(赋值为0,且压入小根堆里面,push(PII(0,s)))first为距离,second为位置 while一下,直到无路可走或者通关 { 提取当前距离到起点最短的点 现提取出来的点的距离可能被上一个点给松弛掉了,直接continue(因为压入的是pair对,距离是当时的距离,不是最近更新的距离,而如果以原本的距离来对往后相连接的点再做一次松弛操作,将不具有最优的最短的距离,应该选择等待新松弛掉的这个点的新数据来对往后的点进行更新) for循环一下,将所连接的点都进行一次更新 如果有所松弛,松弛掉的点就存在可能能够对其后续所连接的点的距离松弛的可能,因而就有必要将这个被当前结点松弛掉的点加入小根堆里面。 } }
代码
int h[N],ne[M],w[M],e[M],idx=0;//ne和e都表示的是边,h表示的是点 void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } typedef pair<int,int > PII; int dist[N]; int dijkstra(int st,int ed) { priority_queue<PII,vector<PII>,greater<PII> > pq; memset(dist,0x3f,sizeof(dist)); pq.push(PII(0,st)); dist[st]=0; while(pq.size()) { PII t = pq.top(); pq.pop(); int d = t.first,u = t.second; if(d>dist[u])continue; for(int i = h[u];~i;i=ne[i]) { int j = e[i]; if(dist[j]>d+w[i]) { dist[j]=d+w[i]; pq.push(PII(dist[j],j)); } } } if(dist[ed]==0x3f3f3f3f) return -1; else return dist[ed]; }
这篇关于dijkstra算法+堆优化 + 链式前向星版本的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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?