（迪杰斯特拉）Dijkstra算法及其优化（C++）-Toy模板网

这篇具有很好参考价值的文章主要介绍了（迪杰斯特拉）Dijkstra算法及其优化（C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目原文

题目描述
给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 $- 1$ 。

输入格式
第一行包含整数 $n$ 和 $m$ 。
接下来 $m$ 行每行包含三个整数 $x, y, z,$ 表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$ 。

输出格式
输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。
如果路径不存在，则输出 $- 1$ 。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

算法思想

算法背景：

迪杰斯特拉算法是由荷兰计算机科学家在1956年发现的算法，是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

算法步骤如下：

初始化过程：初始时令 $S={V_0},T=V-S=$ { 其余顶点 }，T中顶点对应的距离值：
若存在， $d(V_0,V_i)$ 为弧上的权值；
若不存在， $d (V 0, Vi)$ 为 $\infty$ 。
选取最短路径过程：从 $T$ 中选取一个与 $S$ 中顶点有关联边且权值最小的顶点 $W$ ，加入到 $S$ 中。
调整邻接点距离过程：对其余 $T$ 中顶点的距离值进行修改：若加进 $W$ 作中间顶点，从 $V_0$ 到 $V_i$ 的距离值缩短，则修改此距离值。
重复上述步骤2、3，直到 $S$ 中包含所有顶点，即 $W=V_i$ 为止。

算法过程

以 题目原文 中输入样例为例（蓝色代表 $T$ ，橙色代表 $S$ ）：
开始时，1在 $S$ 中，而2、3在 $T$ 中，
（迪杰斯特拉）Dijkstra算法及其优化（C++）

节点	距离
1	0
2	2
3	4

然后将距离为2的边所对应的节点2加入 $S$ 中：
（迪杰斯特拉）Dijkstra算法及其优化（C++）

节点	距离
1	0
2	2
3	3

最后将节点3加入 $S$ 中：
（迪杰斯特拉）Dijkstra算法及其优化（C++）

节点	距离
1	0
2	2
3	3

算法结束，题目所求节点 1 到节点 $n$ 的距离即为 3。

算法代码

当数据范围满足 $1≤n≤500,1≤m≤10^5$ 时，直接使用朴素算法即可。且图为稠密图，结构直接使用邻接矩阵储存即可。

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

当数据范围满足 $1≤n,m≤1.5×10^5$ 时，考虑对算法进行优化。且图为稀疏图，所以采用邻接表存储结构对图进行储存。

优化：原算法时间复杂度为 $O(n^2)$ ，我们可以发现，如果边数远小于 $n^2$ ，对此可以考虑用堆这种数据结构对其进行优化，将最耗时的 选取最短路径过程 的复杂度降为O(1)；此外，使用堆结构后 调整邻接点距离过程 的复杂度变为 $O (m l o g n)$ ；e为该点的边数，所以复杂度降为 $O (m l o g n)$ 。
这里使用优先队列 priority_queue 作为堆。文章来源地址https://www.toymoban.com/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;
}