堆优化版的Dijkstra算法
适用于稀疏图
解题思路
1.因为是模拟的堆所以先用的链队存储已有的路径,所以就有e啊ne啊idx之类的东西,都是模板啦自己记一记,随后再add一下,就是在链表中加入已知路径,这也是模板!!!
2.初始化链队数组,将所有的路径输入,调用优化的Dijkstra函数。
3.优化的Dijkstra函数首先将距离数组初始化,把第一个的距离设为0。
4.关键一步来了,由于升序优先队列模拟的是小根堆,所以堆顶一定是最小距离,取出这个最小距离与所有节点的距离进行更新,若到达该点的距离小于通过当前更新点的距离,那么把该点更新后插入队列。
5.如果最后距离无穷大,那么不存在最短路径。
算法1
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
int e[N],h[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
int dijkstra_h()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//优先队列,用来模拟堆,本质上还是队列,greater代表升序,也就是小根堆。
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});//第一次先放入起点
while(heap.size())
{
auto t=heap.top();//优先队列升序顶最小,每次取出来当前距离最小的点
heap.pop();
int ver=t.second,distance = t.first;//ver存放当前点的编号,distance存放当前点的距离代价
if(st[ver]) continue;//如果已经更新过,那就是冗余备份,跳过
st[ver]=true;
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];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>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_h();
cout<<t<<endl;
return 0;
}