Dijkstra求最短路演算法 ( 超級超級詳細的 ) 不斷更新中

Dijkstra求最短路

最短路問題

先講講樸素版本的

Dijkstra演算法

迪杰斯特拉演算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉演算法，是從一個頂點到其余各頂點的最短路徑演算法，解決的是有權圖中最短路徑問題，迪杰斯特拉演算法主要特點是從起始點開始，采用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止，

我們先看看從1號點到n號點的最短距離怎么求，

實作程序

實作這個程序，我們首先要定義幾個陣列：

int g[N][N];  // 存盤每條邊
int dist[N];  // 存盤1號點到每個點的最短距離
bool st[N];   // 存盤每個點的最短路是否已經確定，若確定則st[i]=true;

S集合表示：當前已經確定最短距離的點，

代碼

int Dijkstra()
{
    memset(dist,0x3f,sizeof dist);//除1號結點外，其他均初始為無窮大
    dist[1]=0;
    for(int i=0;i<n;i++) //n次迭代，每次尋找不在s中距離最近的點t
    {
        int t=-1;// 便于更新第一個點
        for(int j=1;j<=n;j++)
          if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
        st[t]=true;  //將t加到s中
        for(int j=1;j<=n;j++)  //用t更新其他點的距離
          dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1; //路徑不存在
    else return dist[n];
}

是不是對這個代碼和程序感到特別懵逼，來，我們上個圖模擬一遍

如圖1，圖中有三個結點1，2，3，1到2結點距離為2，2到3結點距離為1，1到3結點距離為4，剛開始時，對每個點的dist[]進行初始化，dist[1]=0，dist[2]=0x3f，dist[3]=0x3f， 此時S集合為空，然后我們將距離起點最近的點加入S集合，顯然1號結點距離起點的距離為0，是距離起點最近的，將其加入S集合，（重點強調起點指的是1號結點，S集合是當前已經確定最短距離點的集合）

然后我們用1號結點去更新其他點到起點的最近距離，1結點到2結點距離g[1][2]=2，小于0x3f，則dist[2]=2，1結點到3結點距離g[1][3]=4，小于0x3f，則dist[3]=4，

用1號結點將所有點的距離更新完畢后，此時S集合中有1號結點，接下來我們讓距離我們剛加入的1號結點最近的點加入集合，顯然為2號結點，2號結點進入S集合，此時S集合中有1,2號結點，然后用2號結點去更新3號結點到起點的距離，dist[3]=4大于 dist[2]+1=3,dist[3]被更新為3，最后將3號結點加入S集合，至此，所有點到起始結點的最短距離都已被找出，dist[n]即為n號節點到1號節點的最短距離，

接下來給出模板
樸素版dijkstra演算法
時間復雜是 O(n^2+m), n 表示點數，m 表示邊數

int g[N][N];  // 存盤每條邊
int dist[N];  // 存盤1號點到每個點的最短距離
bool st[N];   // 存盤每個點的最短路是否已經確定

// 求1號點到n號點的最短路，如果不存在則回傳-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在還未確定最短路的點中，尋找距離最小的點
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他點的距離
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

好了接下來我們來看一道模板題，實踐是檢驗真理的唯一標準

AcWing 849. Dijkstra求最短路 I

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值，
請你求出1號點到n號點的最短距離，如果無法從1號點走到n號點，則輸出-1，
輸入格式
第一行包含整數n和m，
接下來m行每行包含三個整數x，y，z，表示存在一條從點x到點y的有向邊，邊長為z，
輸出格式
輸出一個整數，表示1號點到n號點的最短距離，
如果路徑不存在，則輸出-1，
資料范圍
1≤n≤500,
1≤m≤105,
圖中涉及邊長均不超過10000，
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3

完整代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N];    //稠密圖用鄰接矩陣存盤比較節省空間
int dist[N];    //dist[i] i結點到起始點(1號結點)的距離
bool st[N] ;    //st[i] 用于標記i結點的最短路是否確定，若確定st[i]=true;
int n,m;
int Dijkstra()
{
    memset(dist,0x3f,sizeof dist);//除1號結點外，其他均初始為無窮大
    dist[1]=0;
    for(int i=0;i<n;i++) //n次迭代，每次尋找不在s中距離最近的點t
    {
        int t=-1;// 便于更新第一個點
        for(int j=1;j<=n;j++)
          if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
        st[t]=true;  //將t加到s中
        for(int j=1;j<=n;j++)  //用t更新其他點的距離
          dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1; //路徑不存在
    else return dist[n];
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);   //鄰接矩陣的初始化，由于求的是最小值，因此初始為無窮大
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x][y]=min(g[x][y],z); //重邊中去取最小值
    }
    printf("%d\n",Dijkstra());
    return 0;
}

如果有些地方不明白的話，不要著急，接著往下看

常見問題合集

1. 0x3f為什么賦值的時候可以memset(dist,0x3f,sizeof dist)但是到后面驗證的時候必須是if(dist[n]==0x3f3f3f3f)而不能是if(dist[n]==0x3f)
   回答:：memset是按位元組來初始化的，int包含4個位元組，所以初始化之后的值就是0x3f3f3f3f，
2. 為什么要用memset(dist,0x3f,sizeof dist)來初始化
   回答:：0x3f3f3f3f的十進制是1061109567，是1e9級別的（和0x7fffffff一個數量級，0x7fffffff代表了32-bit int的最大值），而一般場合下的資料都是小于1e9的，所以它可以作為無窮大使用而不致出現資料大于無窮大的情形， 另一方面，由于一般的資料都不會大于10^9，所以當我們把無窮大加上一個資料時，它并不會溢位（這就滿足了“無窮大加一個有窮的數依然是無窮大”），事實上0x3f3f3f3f+0x3f3f3f3f=2122219134，這非常大但卻沒有超過32-bit int的表示范圍，所以0x3f3f3f3f還滿足了我們“無窮大加無窮大還是無窮大”的需求，
3. for(int i=0;i<n;i++) { t=-1 } 這里為什么t要賦值為 -1
   回答: 由于每一次都要找到還沒有確定最短路距離的所有點中，距離當前的點最短的點，t = - 1是為了在st這個集合中找第一個點更新時候的方便所設定的，
4. 如果是問編號a到b的最短距離該怎么改呢? （好問題）
   回答： 初始化時將 dist[a]=0,以及回傳時return dist[b]，
5. 自環和重邊對 Dijkstrea演算法有影響嗎？
   回答： 自環在樸素版dijkstra演算法中是沒有任何影響的，所以自環的權值是多少都可以，只要不是負數就行，而重邊時，我們去取重邊中的最小值 即代碼g[x][y]=min(g[x][y],z)，
6. 為什么要用鄰接矩陣去存貯，而不是鄰接表？
   回答： 我們采用鄰接矩陣還是采用鄰接表來表示圖，需要判斷一個圖是稀疏圖還是稠密圖，稠密圖指的是邊的條數|E|接近于|V|2，稀疏圖是指邊的條數|E|遠小于于|V|2（數量級差很多），本題是稠密圖，顯然稠密圖用鄰接矩陣存盤比較節省空間，反之用鄰接表存盤，

問題會持續更新，歡迎評論區留言，