Acwing算法基础课——图论之堆优化的dijkstra算法

思路

首先请看懂我之前发的，dijkstra算法的朴素版本的讲解，既然是优化算法，那肯定是在某个算法的基础上进行优化的，如果基础版本都看不懂，那么直接看这个代码是毫无意义的。

我的朴素迪杰斯特拉讲解

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=510;
int map[N][N];
int s[N];
int d[N];
int n,m;


int Dijkstra(){
    memset(d,0x3f,sizeof(d));
    d[1]=0;
  
    for(int i=0;i<n;i++){
        int t=-1;
        //找到当前未在（已找到最短距离的）集合中的距离1号点最近的点，肯定是需要遍历所有点才能找到的(这里可以用堆进行优化到logn)
        //所以这里会有一个for循环
        for(int j=1;j<=n;j++){
            if(!s[j]&&(t==-1||d[j]<d[t])){
                t=j;
            }
        }
      
        s[t]=true;
        
        //用刚刚找到的点更新其余点到1号点的距离
        for(int j=1;j<=n;j++){
            d[j]=min(d[j],d[t]+map[t][j]);
        }
    }
    
    if(d[n]==0x3f3f3f3f){
        return -1;
    }
    
    return d[n];
}



int main(){
    memset(map,0x3f,sizeof(map)); //首地址，值，长度
    cin>>n>>m;
    int a,b,c;
    
    while(m--){
        cin>>a>>b>>c;
        map[a][b]=min(map[a][b],c); //有向边
    }
    
    int ans=Dijkstra();
    cout<<ans;
    
    return 0;
}

           

可以看到上面查找不在已经找到最短路集合中的最近的点的时候那一步for循环可以用堆优化到logn,整个算法的实践复杂度可以优化到nlogn，所以我们可以对于这一步采用小顶堆进行优化

优化后的代码

#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
const int N=150010;
int h[N],e[N],ne[N],w[N],idx;
int s[N];
int d[N];
int n,m;
typedef pair<int,int> PII;


void add(int x,int y,int c){
    e[idx]=y;
    w[idx]=c;
    ne[idx]=h[x];
    h[x]=idx++;
}



int Dijkstra(){
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//定义小顶堆，升序
    heap.push({0,1});
    
    while(heap.empty()!=true){
        PII k=heap.top();
        heap.pop();
        int ver=k.second;
        int distance=k.first;
        
        if(s[ver]) continue;
        
        s[ver]=true;
        
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];//注意！自己多次忘记这个了！
            if(d[j]>distance+w[i]){
                d[j]=distance+w[i];
                heap.push({d[j],j});
            }
        }
    }
    
    
    if(d[n]==0x3f3f3f3f){
        return -1;
    }
    
    return d[n];
}



int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int a,b,c;
    
    while(m--){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    
    int ans=Dijkstra();
    cout<<ans;
    
    return 0;
}