圖的最短路徑問題 詳細分解版

1.圖的最短路徑問題分類

2.單源最短路問題

2.1邊權值都是正數情况

2.1.1 樸素Dijstra算法

算法思想：每次從未被確定最短距離的結點中找出距離起點最小值的結點，加入集合s中，並用該結點更新其他未被確定最短路徑值得結點路徑。直到最終全部節點的最短路徑值都計算出，此時集合s為所有結點集合。

#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int g[N][N];//稠密圖，鄰接矩陣存儲
int st[N];//是否被訪問過，即是否在s集合中
int dist[N];//記錄每個點到起點的距離
int n,m;
//返回編號為n的結點到1號結點的最短路徑
int dijstra(){
    memset(dist,0x3f,sizeof dist);//將距離初始化為無窮大
    dist[1]=0;//1號結點距離初始化為0
    for(int i=0;i<n;i++){//n輪循環，每次找出一個結點，加入s集合，並用其更新其他節點dist數組。必須有n輪循環，因為要更新dist數組
        int t=-1;
        for(int j=1;j<=n;j++){//循環找出當前距離起始的1號結點最近，且未加入s的結點
            if(!st[j]&&(t==-1||dist[j]<dist[t])){
                t=j;
            }
        }
        st[t]=true;//將該結點加入s數組
        for(int j=1;j<=n;j++){//循環更新其他節點距離
            if(!st[j]){
                dist[j]=min(dist[j],dist[t]+g[t][j]);
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;//如果dist[n]未被更新，說明其不可達
    return dist[n];
}

int main(){
    memset(g,0x3f,sizeof g);//初始化結點間的距離為無窮大
    cin>>n>>m;//輸入數據包含n個結點，m條邊
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;//輸入m條邊，輸入數據存在自環和重邊，取最小值即可
        g[a][b]=min(g[a][b],c);
    }
    cout<<dijstra()<<endl;
    return 0;
}

算法分析：算法包含兩輪循環，時間複雜度為\(O(n^2)\)

2.1.2 堆優化的Dijstra算法

優化思想：樸素Dijstra算法每次都要找出當前距離起點最近的結點，加入集合s中。我們可以使用堆來維護結點距離起點的距離，省去一重循環。

//稀疏圖的dijstra
#include<bits/stdc++.h>
using namespace std;

const int N = 1.5e5+10;

int e[N],ne[N],w[N],h[N],idx;//稀疏圖，采用鄰接錶存儲

int n,m;//n個結點，m條邊

int dist[N];//距離數組
bool st[N];//是否訪問過，即s集合標記

typedef pair<int, int> PII;//使用堆自動排序，pair的first為距離，second為編號

void add(int a,int b,int c){//添加結點a->b的邊，權值為c
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dijstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> q;//聲明小根堆
    q.push({0,1});//1號結點加入隊列
    while(!q.empty()){
        PII t=q.top();
        q.pop();
        int distance=t.first,x=t.second;
        if(st[x]) continue;//距離已經確定，跳過
        st[x]=true;
        for(int i=h[x];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[x]+w[i]<dist[j]){
                dist[j]=dist[x]+w[i];
                q.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

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

算法分析：
時間複雜度：每次找到最小距離的點沿著邊更新其他的點，若dist[j] > distance + w[i]，錶示可以更新dist[j]，更新後再把j點和對應的距離放入小根堆中。由於點的個數是n，邊的個數是m，在極限情况下（稠密圖\(m=\frac{n*n(n-1)}{2}\)）最多可以更新m回，每一回最多可以更新\(n^2\)個點（嚴格上是n - 1個點），有m回，因此最多可以把\(n^2\)個點放入到小根堆中，因此每一次更新小根堆排序的情况是\(O(log(n^2))\)，一共最多m次更新，因此總的時間複雜度上限是\(O(mlog((n^2)))=O(2mlogn)=O(mlogn)\)
疑問：為什麼會存在距離已經確定了點在堆中？
因為可能上次新加入集合s的元素更新了a的距離值，但是距離值很大，直到a的距離值確定了才pop出來。

2.2邊權值存在負數的情况

2.2.1 Bellman-ford算法

算法思想：如果圖中存在n個點，那麼經過n-1次循環，每輪循環時把每條邊都進行松弛操作，若在 n-1 次松弛後還能更新，則說明圖中有負環，因此無法得出結果，否則就完成。
松弛操作：

for n次
	for 所有邊 a,b,w (松弛操作)
		dist[b] = min(dist[b],back[a] + w)

注意：back[] 數組是上一次迭代後 dist[] 數組的備份，由於是每個點同時向外出發，因此需要對 dist[] 數組進行備份，若不進行備份會因此發生串聯效應，影響到下一個點。

在下面代碼中，是否能到達n號點的判斷中需要進行if(dist[n] > INF/2)判斷，而並非是if(dist[n] == INF)判斷，原因是INF是一個確定的值，並非真正的無窮大，會隨著其他數值而受到影響，dist[n]大於某個與INF相同數量級的數即可。

bellman - ford算法擅長解决有邊數限制的最短路問題。

//本代碼是解决有邊數限制的最短路徑問題的代碼
#include<bits/stdc++.h>
using namespace std;

const int N = 10010;
int n,m,k;
int dist[510],backup[510];

struct{
    int a,b,w;
}edges[N];//a->b有一條邊，權重為w

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){//最多k條邊，總共最對經過k條邊
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++){//對所有的m條邊執行松弛操作
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            if(backup[a]+w<dist[b]){
                dist[b]=backup[a]+w;
            }
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -0x3f3f3f3f;
    else return dist[n];
}

int main(){
    cin>>n>>m>>k;
    int a,b,w;
    for(int i=0;i<m;i++){
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }
    int ans=bellman_ford();
    if(ans==-0x3f3f3f3f){
        cout<<"impossible"<<endl;
    }else{
        cout<<ans<<endl;
    }
    
    return 0;
}

算法分析：
時間複雜度：\(O(nm)\),其中n為點數，m為邊數

2.2.2 SPFA算法

算法思想：優化了Bellman-ford算法。在Bellman-ford算法中，dist[b] = min(dist[b],back[a] + w),如果a的距離沒有更新，那麼我的循環其實做了很多沒用的操作。所以我們希望當a的距離更新時 ，再去用a更新其他結點的距離值。算法思想類似於Dijstra算法。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int e[N],w[N],h[N],ne[N],idx;

int n,m;

int st[N];//記錄結點是否在隊列中，即是否發生更新
int dist[N];

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

int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){//松弛操作
                dist[j]=dist[t]+w[i];
                if(!st[j]){//結點發生距離更新，所以可以用該結點去更新其他結點
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -0x3f3f3f3f;
    return dist[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=spfa();
    if(ans==-0x3f3f3f3f) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
    return 0;
}

算法分析：
Bellman_ford算法裏最後return -1的判斷條件寫的是dist[n]>0x3f3f3f3f/2;而spfa算法寫的是dist[n]==0x3f3f3f3f;其原因在於Bellman_ford算法會遍曆所有的邊，因此不管是不是和源點連通的邊它都會得到更新；但是SPFA算法不一樣，它相當於采用了BFS，因此遍曆到的結點都是與源點連通的，因此如果你要求的n和源點不連通，它不會得到更新，還是保持的0x3f3f3f3f。

Bellman_ford算法可以存在負權回路，是因為其循環的次數是有限制的因此最終不會發生死循環；但是SPFA算法不可以，由於用了隊列來存儲，只要發生了更新就會不斷的入隊，因此假如有負權回路請你不要用SPFA否則會死循環。

由於SPFA算法是由Bellman_ford算法優化而來，在最壞的情况下時間複雜度和它一樣即時間複雜度為 \(O(nm)\) ，假如題目時間允許可以直接用SPFA算法去解Dijkstra算法的題目。

求負環一般使用SPFA算法，方法是用一個cnt數組記錄每個點到源點的邊數，一個點被更新一次就+1，一旦有點的邊數達到了n那就證明存在了負環。

3.多源匯最短路徑問題

Floyd算法

算法思想：三重循環，動態規劃思想。\(dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\)

#include<bits/stdc++.h>
using namespace std;

const int N = 510,INF=1e9;

int g[N][N];//g[i][j]記錄i->j的最短路徑

int n,m,Q;

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}

int main(){
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++){//初始化數組
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }
    while(m--){//輸入m條邊
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    
    
    floyd();
    
    while(Q--){//Q次查詢
        int a,b;
        cin>>a>>b;
        if(g[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<g[a][b]<<endl;
    }
    
    return 0;
}

算法分析：三重循環，floyd算法時間複雜度為\(O(n)\)