題目原文

題目描述
給定一個 $n$ 個點(diǎn) $m$ 條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為非負(fù)值。
請你求出 $1$ 號點(diǎn)到 $n$ 號點(diǎn)的最短距離，如果無法從 $1$ 號點(diǎn)走到 $n$ 號點(diǎn)，則輸出 $?1$。

輸入格式
第一行包含整數(shù) $n$ 和 $m$。
接下來 $m$ 行每行包含三個整數(shù) $x,y,z,$ 表示存在一條從點(diǎn) $x$ 到點(diǎn) $y$ 的有向邊，邊長為 $z$。

輸出格式
輸出一個整數(shù)，表示 $1$ 號點(diǎn)到 $n$ 號點(diǎn)的最短距離。
如果路徑不存在，則輸出 $?1$。

輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

輸出樣例：

3

算法思想

算法背景：

迪杰斯特拉算法是由荷蘭計算機(jī)科學(xué)家在1956年發(fā)現(xiàn)的算法，是從一個頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是從起始點(diǎn)開始，采用貪心算法的策略，每次遍歷到始點(diǎn)距離最近且未訪問過的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。

算法步驟如下：

1. 初始化過程：初始時令 $S=V_0,T=V?S=$ { 其余頂點(diǎn) }，T中頂點(diǎn)對應(yīng)的距離值：
   若存在，$d(V_0,V_i)$ 為弧上的權(quán)值；
   若不存在，$d(V0,Vi)$ 為 $\infty$。
2. 選取最短路徑過程：從 $T$ 中選取一個與 $S$ 中頂點(diǎn)有關(guān)聯(lián)邊且權(quán)值最小的頂點(diǎn) $W$ ，加入到 $S$ 中。
3. 調(diào)整鄰接點(diǎn)距離過程：對其余 $T$ 中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn) $W$ 作中間頂點(diǎn)，從 $V_0$ 到 $V_i$ 的距離值縮短，則修改此距離值。
   重復(fù)上述步驟2、3，直到 $S$ 中包含所有頂點(diǎn)，即 $W=V_i$為止。

算法過程

以 題目原文 中輸入樣例為例（藍(lán)色代表 $T$，橙色代表 $S$）：
開始時，1在 $S$ 中，而2、3在 $T$ 中，

然后將距離為2的邊所對應(yīng)的節(jié)點(diǎn)2加入 $S$ 中：

最后將節(jié)點(diǎn)3加入 $S$ 中：

算法結(jié)束，題目所求節(jié)點(diǎn) 1 到節(jié)點(diǎn) $n$ 的距離即為 3。

算法代碼

1. 當(dāng)數(shù)據(jù)范圍滿足 $1\le n\le 500,1\le m\le 10^5$ 時，直接使用樸素算法即可。且圖為稠密圖，結(jié)構(gòu)直接使用鄰接矩陣儲存即可。

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

using namespace std;

const int N = 510;

int g[N][N], d[N];
bool st[N];
int n, m;

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

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    cout << dijkstra() << endl;
    return 0;
}

2. 當(dāng)數(shù)據(jù)范圍滿足 $1\le n,m\le 1.5\times 10^5$ 時，考慮對算法進(jìn)行優(yōu)化。且圖為稀疏圖，所以采用鄰接表存儲結(jié)構(gòu)對圖進(jìn)行儲存。

優(yōu)化：原算法時間復(fù)雜度為 $O(n^2)$ ，我們可以發(fā)現(xiàn)，如果邊數(shù)遠(yuǎn)小于 $n^2$，對此可以考慮用堆這種數(shù)據(jù)結(jié)構(gòu)對其進(jìn)行優(yōu)化，將最耗時的 選取最短路徑過程 的復(fù)雜度降為O(1)；此外，使用堆結(jié)構(gòu)后 調(diào)整鄰接點(diǎn)距離過程 的復(fù)雜度變?yōu)?$O(mlogn)$；e為該點(diǎn)的邊數(shù)，所以復(fù)雜度降為 $O(mlogn)$。
這里使用優(yōu)先隊列 priority_queue 作為堆。文章來源地址http://www.zghlxwxcb.cn/news/detail-406318.html

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

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5;

int n, m, idx = -1;
int h[N], ne[N], w[N], e[N];
int d[N];
bool st[N];

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

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())
    {
        auto item = heap.top();
        heap.pop();
        
        int dist = item.first, node = item.second;
        
        if (st[node]) continue;
        st[node] = true;
        
        for (int i = h[node]; i != -1; i = ne[i])
        {
            if (d[e[i]] > dist + w[i]) 
            {
                d[e[i]] = dist + w[i];
                heap.push({d[e[i]], e[i]});
            }
        }
    }
    
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    cout << dijkstra() << endl;
    return 0;
}

到了這里，關(guān)于（迪杰斯特拉）Dijkstra算法及其優(yōu)化（C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！