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