文章目录

一、Dijkstra 算法

1. 简介

2. 基本思想

3. 朴素 Dijkstra 算法（重点）

3.1 朴素 Dijkstra 算法实现步骤

3.2 朴素 Dijkstra 算法伪代码

4. 朴素 Dijkstra 算法具体实现详见例题 Dijkstra 求最短路 I 。

5. 堆优化朴素 Dijkstra 算法

6. 堆优化 Dijkstra 算法具体实现详见例题 Dijkstra 求最短路 II 。

7. 堆优化 Dijkstra 算法和朴素 Dijkstra 算法时间复杂度

二、Dijkstra 算法例题——Dijkstra 求最短路 I

具体实现

1. 样例演示

2. 实现思路

3. 代码注解

4. 实现代码

三、Dijkstra 算法例题——Dijkstra求最短路 II

具体实现

1. 样例演示

2. 实现思路

3. 代码注解

4. 实现代码

一、Dijkstra 算法

1. 简介

Dijkstra（迪杰斯特拉）算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。

这是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

迪杰斯特拉算法主要特点是从起始点开始，采用 贪心算法 的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

此算法不能用于求负权图，要求所有边的权重都为非负值。

2. 基本思想

1） 首先假定源点为 u ，顶点集合 V 被划分为两部分：集合 S 和 V-S。 初始时 S 中仅含有源点 u ，其中 S 中的顶点到源点的最短路径已经确定。

（2） 集合 S 和 V-S 中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过 S 中的点到达 V-S 中的点的路径为特殊路径，并用 dist[] 记录当前每个顶点对应的最短特殊路径长度。

3. 朴素 Dijkstra 算法（重点）

3.1 朴素 Dijkstra 算法实现步骤

（1） 各个点状态初始化，各点之间距离初始化。

用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。

用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。

（2） 源点到源点的距离为 0，即 dist[1] = 0

（3） 遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i 。此时就找到了源点到该节点的最短距离，state[i] 置为 1 。

4） 遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist[i] 加上 i -> j 的距离，即 dist[j] > dist[i] + w[i][j]（w[i][j] 为 i -> j 的距离） ，则更新 dist[j] = dist[i] + w[i][j] 。

5） 重复 3 4 步骤，直到所有节点的状态都被置为 1。

• （6） 此时 dist 数组中，就保存了源点到其余各个节点的最短距离。

.2 朴素 Dijkstra 算法伪代码

int dist[n],state[n];
dist[1] = 0, state[1] = 1;
for(i:1 ~ n)
{
    t <- 没有确定最短路径的节点中距离源点最近的点;
    state[t] = 1;
    更新 dist;
}

4. 朴素 Dijkstra 算法具体实现详见例题 Dijkstra 求最短路 I 。

5. 堆优化朴素 Dijkstra 算法

• 朴素 Dijkstra 算法的主要耗时的步骤是从 dist 数组中选出，没有确定最短路径的节点中距离源点最近的点 t 。只是找个最小值而已，没有必要每次遍历一遍 dist 数组。
• 在一组数中每次能很快的找到最小值，很容易想到使用小根堆。可以使用库中的小根堆（推荐）或者自己编写。

具体思路如下：

（1） 起始点的距离初始化为零，其他点初始化成无穷大。

（2） 将起始点放入堆中。

（4） 不断循环，直到堆空。每一次循环中执行的操作为：弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定），用该点更新临界点的距离，若更新成功就加入到堆中。

6. 堆优化 Dijkstra 算法具体实现详见例题 Dijkstra 求最短路 II 。

7. 堆优化 Dijkstra 算法和朴素 Dijkstra 算法时间复杂度

• 朴素 Dijkstra 算法时间复杂度 O(n²) 。

for (int i = 0; i < n; i++) 
{
    int t = -1;
    for (int j = 1; j <= n; j++)
    {
        if (!st[j] && (t == -1 || dist[j] < dist[t]))
            t = j; // O(n) * O(n) -> O(n^2)
    }
    st[t] = true; // O(n) * O(1) -> O(n)
    for (int j = 1; j <= n; j++)
    {
        dist[j] = min(dist[j], dist[t] + g[t][j]); //O(n) * O(n) -> O(n^2)
    }
}

• 堆优化 Dijkstra 算法时间复杂度 O(mlog(n)) 。

//遍历大部分的边
    while (heap.size()) 
    {
        auto t = heap.top(); //O(m) * O(1) -> O(m)
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver])
        {
            continue;
        }
        st[ver] = true;  //O(m) * O(1) -> O(m)
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i]) 
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
                // 堆的插入操作时间复杂度是 O(log(n))
                // O(m) * O(log(n)) -> O(mlog(n))
            }
        }
    }

二、Dijkstra 算法例题——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 ≤ 1e5

图中涉及边长均不超过10000 。

输入样例

3 3

1 2 2

2 3 1

1 3 4

输出样例

3

具体实现

1. 样例演示

• 输入 n = 3，m = 3，表示求从 1 号点到 n = 3 号点的最短距离，共有 m = 3 条边。
• 从 1 号点到 2 号点的边长为 2 。
• 从 2 号点到 3 号点的边长为 1 。
• 从 1 号点到 3 号点的边长为 4 。

• 显然，1 + 2 小于 4 ，因此最短路径存在，且为 3 。

2. 实现思路

在此只作简单叙述，具体可见朴素 Dijkstra 算法实现步骤和样例演示。

（1） 初始化各点到起点距离为正无穷。

（2） 将 1 号点到起点的距离更新为 0 。

（3） 2 号点到 1 号点的距离为 2 ，小于正无穷，将其更新为 2 ； 3 号点同理，将距离更新为 4 。

（4） 然后，2 和 4 的最小值是 2 ，便将 2 加入集合 s ，此时，2 号点到 3 号点的距离 1 。可得，2 + 1 ＜ 4，便将 3 号点到起点的距离更新为 3 。

3. 代码注解

int g[N][N]；稠密图一般使用邻接矩阵。

int dist[N]；记录每个节点距离起点的距离。

bool st[N]；true 表示已经确定最短路 属于 s 集合。

memset(dist, 0x3f, sizeof dist)；所有节点距离起点的距离初始化为无穷大。

dist[1] = 0；起点距离自己的距离为零。

int t = -1；一开始 t 的赋值是 -1 ，如果 t 没有被更新，那么要更新一下 t 。

memset 按字节赋值，所以 memset 0x3f 就等价与赋值为 0x3f3f3f3f 。

其他代码注解已标注在实现代码当中，详见实现代码。

4. 实现代码

#include <bits/stdc++.h>
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;
    //迭代n次，每次可以确定一个点到起点的最短路
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
        {
            //不在s集合，并且
            //如果没有更新过，则进行更新， 或者发现更短的路径，则进行更新
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
        //加入到s集合中
        st[t] = true;
    }
    // 如果起点到达不了n号节点，则返回-1
    if (dist[n] == 0x3f3f3f3f) 
    {
        return -1;
    }
    // 返回起点距离n号节点的最短距离
    return dist[n];
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra() << endl;
    system("pause");
    return 0;
}

三、Dijkstra 算法例题——Dijkstra求最短路 II

题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

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

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1 ≤ n,m ≤ 1.5×1e5

图中涉及边长均不小于 0，且不超过 10000。

数据保证：如果最短路存在，则最短路的长度不超过 1e9。

输入样例

3 3

1 2 2

2 3 1

1 3 4

输出样例

3

具体实现

1. 样例演示

• 同 Dijkstra 算法例题——Dijkstra求最短路 I 。

2. 实现思路

• 不需要手写堆，使用 C++ 当中的优先队列。
• 小根堆使用 greater 实现。

3. 代码注解

typedef pair<int, int> PII；<离起点的距离， 节点编号>。

memset(dist, 0x3f, sizeof dist)；所有距离初始化为无穷大。

dist[1] = 0；1 号节点距离起点的距离为 0 。

priority_queue<PII, vector, greater> heap；建立一个小根堆。

其他代码注解已标注在实现代码当中，详见实现代码。

4. 实现代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;//<离起点的距离， 节点编号>
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
//在 a 节点之后插入一个 b 节点，权重为 c
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    //1号节点插入堆
    heap.push({0, 1});
    while (heap.size())
    {
        //取出堆顶顶点
        auto t = heap.top();
        //并删除
        heap.pop();
        //取出节点编号和节点距离
        int ver = t.second;
        int distance = t.first;
        //如果节点被访问过则跳过
        if (st[ver]) 
        {
            continue;
        }
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            //取出节点编号
            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()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    system("pause");
    return 0;
}