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];
}