• 博主簡介：努力學(xué)習(xí)的大一在校計算機專業(yè)學(xué)生，熱愛學(xué)習(xí)和創(chuàng)作。目前在學(xué)習(xí)和分享：算法、數(shù)據(jù)結(jié)構(gòu)、Java等相關(guān)知識。
• 博主主頁： @是瑤瑤子啦
• 所屬專欄: 算法 ；該專欄專注于藍(lán)橋杯和ACM等算法競賽??
• 近期目標(biāo)：寫好專欄的每一篇文章

一、簡介

Dijkstra算法適用于最短路問題中，單源最短路（只有一個起點），并且每條邊的權(quán)重都是正數(shù)的情況

二、基本思想策略

首先假定源點為u（就是起點），頂點集合V被劃分為兩部分：集合 S 和 V-S。 初始時S中僅含有源點u，其中S中的頂點到源點的最短路徑已經(jīng)確定。
集合S 和V-S中所包含的頂點到源點的最短路徑的長度待定，稱從源點出發(fā)只經(jīng)過S中的點到達V-S中的點的路徑為特殊路徑（不一定是最短的）
并用dist[]記錄當(dāng)前每個頂點對應(yīng)的最短特殊路徑長度。

紅色頂點是S集合中，均已經(jīng)確定最短路徑的點，而綠色的是V-S集合中沒有確定該頂點到源點最短路徑的點。我們可以看到只經(jīng)過S中的點到綠色點有兩條特殊路徑：15+20和20+10，但是只有一條最短路徑：15+20，那么綠色點就當(dāng)前情況來看，可以暫時把它的dist[i]更新為25，但是一定是最短特殊路徑嗎？不一定，為什么呢？我們接下來往下看

可以看到，V-S集合中假設(shè)存在一點T，經(jīng)過這點到目的點的距離，很有可能是目的點真正的dist！

可能這里可能有點暈，沒錯。上面只是一個大概的介紹，我們接下來徹底揭開它的神秘面紗。

選擇特殊路徑長度最短的路徑，將其連接的V-S中的頂點加入到集合S中，同時更新數(shù)組dist[]（核心）。一旦S包含了所有頂點，dist[]就是從源到所有其他頂點的最短路徑長度。

數(shù)據(jù)結(jié)構(gòu): h[N],e[M],ne[M],w[M]構(gòu)建帶權(quán)重的鄰接表，來存儲圖;int dist[N];//dist 數(shù)組保存源點到其余各個節(jié)點的距離

（1）初始化。令集合S={0}，對于集合V-S中的所有頂點x{1，2，3…n}；初始化dist數(shù)組memset(dist, 0x3f, sizeof(dist));//dist 數(shù)組的各個元素為無窮大,

（2）找最小。在集合V-S中依照貪心策略來尋找使得dist[j]具有最小值的頂點t,即dist[t]=min，則頂點t就是集合V-S中距離源點u最近的頂點。
（3）加入S戰(zhàn)隊。將頂點t加入集合S，同時更新V-S
（4）借東風(fēng)。在（2）中已近找到了源點到t的最短路徑，那么對集合V-S中所有與頂點t相鄰的頂點j，都可以借助t走捷徑。
如果dist[i] = min(dist[i], dist[t] + w[j]);//更新 dist[j]，轉(zhuǎn)（2）。

光憑這個好像是這么回事，但是細(xì)節(jié)值得推敲。這個題的本質(zhì)還是貪心。
比如只看剛剛的文字，不仔細(xì)分析，你能不能解決我開頭提出的那個問題？
為什么這么說呢。因為在目前（局部情況）來看，確實找到最短特殊路徑了，竟然就直接加入S戰(zhàn)隊，不太可取，就像我開頭提出的，在V-S集合中，萬一存在一個點，經(jīng)過這個點再到目的點，很有可能才是真正的最短距離。
那為什么這個算法是可取的呢？
巧就巧在，最外層循環(huán)，遍歷了整個頂點，并且并不是說，一旦該頂點加入了S戰(zhàn)隊，它的dist就不能變了，相反，它在實時更新！。當(dāng)循環(huán)遍歷到綠色頂點T時，會更新與它相連節(jié)點的dist。
不知道有沒有g(shù)et到我的意思，雖然我沒有用公式啥的去推導(dǎo)，我個人也非常討厭那種不人性化的方式，更喜歡用一種形象的，意會的方式去理解。

綜上，由局部最優(yōu)，到全局最優(yōu)，這種貪心的策略，完全可以保證全部遍歷和循環(huán)后，dist[]數(shù)組中存的就是該點到源點的最短距離?。。。ㄉ厦媸俏覀€人的理解，歡迎一起討論交流和學(xué)習(xí)捏?。?/p>

三、代碼實現(xiàn)

這里是AcWing 849.Dijkstra求最短路 I模板題目

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為正值。

請你求出 1 號點到 n 號點的最短距離，如果無法從 1 號點走到 n 號點，則輸出 ?1。

輸入格式

第一行包含整數(shù) n 和 m。

接下來 m 行每行包含三個整數(shù) x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z。

輸出格式

輸出一個整數(shù)，表示 1 號點到 n 號點的最短距離。

如果路徑不存在，則輸出 ?1。

數(shù)據(jù)范圍

1≤n≤500,
1≤m≤105,
圖中涉及邊長均不超過10000。

3.1偽代碼詳解

int dist[N],state[N];
dist[1] = 0,state = 1;//把源點加入S集合
for (i : 1~n)
{
  1),t<-找最小，找到只經(jīng)過S中的點到V-S集合中某一點，距離最小的那個V-S中的那個點
  2),state[t] = 1;將t加入到S戰(zhàn)隊
   3),更新與t頂點相鄰點的dist
  
}

3.2源代碼詳解

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

using namespace std;

//N是頂點數(shù)，M是邊數(shù)
const int N =510,M = 100010;
int h[N],e[M],ne[M],w[M],idx;//鄰接表存儲圖，w[M]存儲邊的權(quán)重
int state[N];//state記錄是否找到了源點到該節(jié)點的最短距離
int dist[N];//dist保存源點到其余各個頂點的最短特殊距離
int n,m;//圖的頂點數(shù)和邊數(shù)

void add(int a,int b,int c)//插入邊，并給每個邊賦值權(quán)重
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a],h[a] = idx++;
}
//key:核心和關(guān)鍵部分！??！
void Dijkstra()
{
    memset(dist,0x3f,sizeof(dist));// 1)初始化dist數(shù)組
    
    dist[1] = 0;//源點到源點的距離當(dāng)然是0
    
    for (int i = 0; i < n; i++)//對n個頂點進行n次遍歷（一開始V-S集合為n個元素,S集合是0個，肯定是遍歷n次，才能完全遍歷完
    {
        int t = -1;//t存儲當(dāng)前這次遍歷到的V-S集合中的點，該點當(dāng)前局部情況距離源點距離最小的那個點
        //2)在V-S中 找最小
        for (int j = 1; j <= n; j++){
            if(!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        state[t] = 1;//3)加入S 戰(zhàn)隊
        
        //3）借東風(fēng)
        for (int j = h[t];j != -1; j = ne[j])
        {
            int i = e[j];
            dist[i] = min(dist[i],dist[t]+w[j]);//更新dist[j]
        }                                                    
    }
}

int main(){
    memset (h,-1,sizeof (h));//初始化鄰接表
    
    cin >> n >>m;
    while (m--)//讀入m條邊
    {
        int a,b,w;
        cin >> a >> b >> w;
        add (a,b,w);
    }
    Dijkstra();
    if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了，那么一定存在從1號節(jié)點到n號節(jié)點的最短距離路徑
        cout << dist[n];
    else
        cout << "-1";
}

關(guān)于存儲圖的適合，沒有考慮重邊和自環(huán)的影響？

因為在第三步更新的時候，即使鄰接表那條單鏈上有兩個一樣編號的節(jié)點，但是第三步更新的時候，還是會讓對應(yīng)編號節(jié)點的dist為最小。所以即使有重邊也不影響

3.4：數(shù)據(jù)結(jié)構(gòu)優(yōu)化

上面我們是采用鄰接表來存儲圖，鄰接表的原理如下。鄰接表是適合稀疏圖，當(dāng)邊比較多，也就是稠密圖時，我們采用鄰接矩陣來存儲圖。即g[a][b]的值為編號為a的節(jié)點a到編號為b的節(jié)點b之間的距離。

使用鄰接矩陣，注意去重邊，因為鄰接矩陣只允許a→b的距離唯一。

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

using namespace std;

const int N = 510;

int n,m;

int g[N][N];//鄰接矩陣存儲圖
int dist[N];
bool st[N];

int dijkstra(){
    memset(dist,0x3f,sizeof(dist)); 
    
    dist[1] = 0;
    
    for(int i = 0; i < n; i++){
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1|| dist[t] > dist[j]))
                t = j;
        
        st[t] = true;
        
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);//初始化鄰接矩陣
    
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b],c);//去除重邊
    }
    int t = dijkstra();
    
    printf("%d\n",t);
    
    return 0;
}

3.3：算法分析

算法時間復(fù)雜度：時間復(fù)雜是 O(n2+m)O(n2+m), n 表示點數(shù)，m表示邊數(shù)

耗時的主要地方在于第2)步，找最小，每次都需要遍歷一遍dist數(shù)組，完全沒有必要?？梢允褂?strong>小根堆來優(yōu)化（小根堆的數(shù)據(jù)結(jié)構(gòu)可以自己來實現(xiàn)（推薦），或者用庫中的）

四、使用小根堆來優(yōu)化Dijkstra算法

這個定義的heap，完全可以看作集合V-S的具體化！通過這個小根堆，可以直接取出（取出+刪除）V-S集合的最小值。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的頭文件

using namespace std;

typedef pair<int, int> PII;//堆里存儲距離和節(jié)點編號

const int N = 1e6 + 10;

int n, m;//節(jié)點數(shù)量和邊數(shù)
int h[N], w[N], e[N], ne[N], idx;//鄰接表存儲圖
int dist[N];//存儲距離
bool st[N];//存儲狀態(tài)

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//距離初始化為無窮大
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
    heap.push({0, 1});//插入距離和節(jié)點編號

    while (heap.size())
    {
        auto t = heap.top();//取距離源點最近的點
        heap.pop();

        int ver = t.second, distance = t.first;//ver:節(jié)點編號，distance:源點距離ver 的距離

        if (st[ver]) continue;//如果距離已經(jīng)確定，則跳過該點
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的節(jié)點距離
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});//距離變小，則入堆
            }
        }
    }

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

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

使用小根堆后，找到 t 的耗時從 O(n^2) 將為了 O(1)。每次更新 dist 后，需要向堆中插入更新的信息。所以更新dist的時間復(fù)雜度有 O(e) 變?yōu)榱?O(elogn)。總時間復(fù)雜度有 O(n^2) 變?yōu)榱?O(n + elongn)。適用于稀疏圖。

五、深入和反思

最開始我們說到，Dijkstra算法只適用于邊的權(quán)重都是正數(shù)的情況。為什么負(fù)權(quán)邊不行呢？

看一個Dijkstra算法失效的例子：

A→B→D→E，確定dist[E]=20，dist[D]=8

然后A→C→D雖然更新了D點的dist，使之正確dist[D]=-1,但是由于D已經(jīng)被遍歷過，無法通過D來更新E，導(dǎo)致最終求出的A→E的最小距離出錯。

為什么呢？

D的dist的正確性不受負(fù)權(quán)的影響，是因為負(fù)權(quán)指向的是D，在更新節(jié)點，更新dist的時候，會更新掉D的錯誤值。但E就不一樣了，在當(dāng)前局部，只有D一個經(jīng)過它，D一旦遍歷過后，更新了E。當(dāng)經(jīng)過C到D時，無法再通過正確的D去更新E！

如果全部是正值的話，在A→D時，能一下子確定當(dāng)前真正的dist[D]！再dist[D]+12，那dist[E]也是正確的！

所以根本原因在于，存在負(fù)權(quán)邊，dist[D]的真值不能在更新dist[E]之前確定。

最后是我個人總結(jié)的理解：

??在Dijkstra算法視角，把B遍歷并進行相關(guān)更新后，它當(dāng)前得知了如下情況：dist[A] = 0,dist[B] = 2,dist[D] = 5,dist[C] = 999,dist[D] = 999+C,C>0,Dijkstra當(dāng)然會放棄A-C-D這條路，可是C其實<0,這條路不該被放棄，反而A-C-D的路徑長度很有可能會小于A-B-C的長度，正是由于Dijkstra的這點輸入，導(dǎo)致出現(xiàn)負(fù)權(quán)邊時，結(jié)果不正確，再說，人家的正確性本來就是建立在所有邊的權(quán)重都>0的基礎(chǔ)上！

文章來源地址http://www.zghlxwxcb.cn/news/detail-401475.html

• Java島冒險記【從小白到大佬之路】
  
• LeetCode每日一題–進擊大廠
• 算法

到了這里，關(guān)于【最短路算法】一篇文章徹底弄懂Dijkstra算法|多圖解+代碼詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！