迪杰斯特拉算法的堆优化

性能

使得最短路算法时间复杂度再次加快了一个档次变成了$n*\log_2 n$n∗log2​n，让人更加头秃

原理

来说原理的话我建议可以讲一下迪杰斯特拉的算法思想，利用贪心，每一次走距离当前点$u$u最近的点$v$v，那么我们由原点到$v$v一定会是最近的，因为$u$u一开始就是最近的，那么$dis[u]+min(u\rightarrow v)\leq dis[u]+!min(u\rightarrow v)$dis[u]+min(u→v)≤dis[u]+!min(u→v)根据这个我们可以知道我们只需

1. 维护一个最小堆来得到当前最小的$dis[u]$dis[u]得到$u$u的位置，然后找到$u$u能到的点$v$v的最短路径，得到$dis[v]$dis[v]然后加入堆
2. 循环1操作直到堆为空就好了。

代码

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 2e+5;
struct ED{
    int pre,id,w;
}ed[N];
int head[N],tot=0,dis[N],vis[N];
void add(int u,int v,int w){
    ed[++tot].pre=head[u];
    ed[tot].id=v;
    ed[tot].w=w;
    head[u]=tot;
}
priority_queue<pair<int,int> >q;
void dij_heap(int x){
    int i;
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[x]=0;
    q.push(make_pair(0,x));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(i=head[u];i;i=ed[i].pre){
            if(dis[u]+ed[i].w<=dis[ed[i].id]){
                dis[ed[i].id]=dis[u]+w;
                q.push(-dis[ed[i].id],ed[i].id);//这里用负数使最大堆变最小堆
            }
        }
    }
}
int main(){
    dij_heap();
    return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

为秃头而生 发布了21 篇原创文章 · 获赞 6 · 访问量 1220 私信 关注