Dijkstra算法，你的最短路来了！

录友们，最近我在图论方面已经开始更最短路系列了，讲好最短路问题，其实也是很难的，本篇我仅仅是讲了朴素版Dijkstra，但就写了将近1w字，画了二十张图。学算法易，讲清楚难！

题目链接

【题目描述】

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

【输入描述】

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

【输出描述】

输出一个整数，代表小明在途中和其他科学家和科研团队交流所花费的最少时间。

输入示例

输出示例：12

【提示信息】

能够到达的情况：

如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。

不能到达的情况：

如下图所示，当从起始车站不能到达终点车站时，则输出 -1。

数据范围：

1 <= N <= 500;
1 <= M <= 5000;

思路

本题就是求最短路，最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。

接下来，我们来详细讲解最短路算法中的 dijkstra 算法。

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

dijkstra 算法可以同时求起点到所有节点的最短路径
权值不能为负数

（这两点后面我们会讲到）

如本题示例中的图：

起点（节点1）到终点（节点7）的最短路径是图中标记绿线的部分。

最短路径的权值为12。

其实 dijkstra 算法和我们之前讲解的prim算法思路非常接近，如果大家认真学过prim算法，那么理解 Dijkstra 算法会相对容易很多。（这也是我要先讲prim再讲dijkstra的原因）

dijkstra 算法同样是贪心的思路，不断寻找距离源点最近的没有访问过的节点。

这里我也给出 dijkstra三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

大家此时已经会发现，这和prim算法怎么这么像呢。

我在prim算法讲解中也给出了三部曲。 prim 和 dijkstra 确实很像，思路也是类似的，这一点我在后面还会详细来讲。

在dijkstra算法中，同样有一个数组很重要，起名为：minDist。

minDist数组用来记录每一个节点距离源点的最小距离。

理解这一点很重要，也是理解 dijkstra 算法的核心所在。

大家现在看着可能有点懵，不知道什么意思。

没关系，先让大家有一个印象，对理解后面讲解有帮助。

我们先来画图看一下 dijkstra 的工作过程，以本题示例为例：（以下为朴素版dijkstra的思路）

（示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样下标和节点标号就可以对应上了，避免大家搞混）

朴素版dijkstra

模拟过程

0、初始化

minDist数组数值初始化为int最大值。

这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。

（图中，max 表示默认值，节点0 不做处理，统一从下标1 开始计算，这样下标和节点数值统一，方便大家理解，避免搞混）

源点（节点1）到自己的距离为0，所以 minDist[1] = 0

此时所有节点都没有被访问过，所以 visited数组都为0

以下为dijkstra 三部曲

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

更新 minDist数组，即：源点（节点1）到节点2 和节点3的距离。

源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[4] = 4

可能有录友问：为啥和 minDist[2] 比较？

再强调一下 minDist[2] 的含义，它表示源点到节点2的最短距离，那么目前我们得到了源点到节点2的最短距离为1，小于默认值max，所以更新。 minDist[3]的更新同理

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点到节点2距离最近，选节点2

2、该最近节点被标记访问过

节点2被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

更新 minDist数组，即：源点（节点1）到节点6 、节点3 和节点4的距离。

为什么更新这些节点呢？怎么不更新其他节点呢？

因为源点（节点1）通过已经计算过的节点（节点2）可以链接到的节点有节点3，节点4和节点6.

更新 minDist数组：

源点到节点6的最短距离为5，小于原minDist[6]的数值max，更新minDist[6] = 5
源点到节点3的最短距离为3，小于原minDist[3]的数值4，更新minDist[3] = 3
源点到节点4的最短距离为6，小于原minDist[4]的数值max，更新minDist[4] = 6

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点距离哪些节点最近，怎么算的？

其实就是看 minDist数组里的数值，minDist 记录了源点到所有节点的最近距离，结合visited数组筛选出未访问的节点就好。

从上面的图，或者从minDist数组中，我们都能看出未访问过的节点中，源点（节点1）到节点3距离最近。

2、该最近节点被标记访问过

节点3被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点3的加入，那么源点可以有新的路径链接到节点4 所以更新minDist数组：

更新 minDist数组：

源点到节点4的最短距离为5，小于原minDist[4]的数值6，更新minDist[4] = 5

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，有节点4 和节点6，距离源点距离都是 5 （minDist[4] = 5，minDist[6] = 5），选哪个节点都可以。

2、该最近节点被标记访问过

节点4被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点4的加入，那么源点可以链接到节点5 所以更新minDist数组：

源点到节点5的最短距离为8，小于原minDist[5]的数值max，更新minDist[5] = 8

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点6，距离源点距离是 5 （minDist[6] = 5）

2、该最近节点被标记访问过

节点6 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点6的加入，那么源点可以链接到节点7 所以更新minDist数组：

源点到节点7的最短距离为14，小于原minDist[7]的数值max，更新minDist[7] = 14

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点5，距离源点距离是 8 （minDist[5] = 8）

2、该最近节点被标记访问过

节点5 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点5的加入，那么源点有新的路径可以链接到节点7 所以更新minDist数组：

源点到节点7的最短距离为12，小于原minDist[7]的数值14，更新minDist[7] = 12

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点7（终点），距离源点距离是 12 （minDist[7] = 12）

2、该最近节点被标记访问过

节点7 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

节点7加入，但节点7到节点7的距离为0，所以不用更新minDist数组

最后我们要求起点（节点1）到终点（节点7）的距离。

再来回顾一下minDist数组的含义：记录每一个节点距离源点的最小距离。

那么起到（节点1）到终点（节点7）的最短距离就是 minDist[7] ，按上面举例讲解来说，minDist[7] = 12，节点1 到节点7的最短路径为 12。

路径如图：

在上面的讲解中，每一步我都是按照 dijkstra 三部曲来讲解的，理解了这三部曲，代码也就好懂的。

代码实现

本题代码如下，里面的三部曲我都做了注释，大家按照我上面的讲解来看如下代码：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;}int start = 1;int end = n;// 存储从源点到每个节点的最短距离std::vector<int> minDist(n + 1, INT_MAX);// 记录顶点是否被访问过std::vector<bool> visited(n + 1, false);minDist[start] = 0;  // 起始点到自身的距离为0for (int i = 1; i <= n; i++) { // 遍历所有节点int minVal = INT_MAX;int cur = 1;// 1、选距离源点最近且未访问过的节点for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}visited[cur] = true;  // 2、标记该节点已被访问// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径}

时间复杂度：O(n^2)
空间复杂度：O(n^2)

debug方法

写这种题目难免会有各种各样的问题，我们如何发现自己的代码是否有问题呢？

最好的方式就是打日志，本题的话，就是将 minDist 数组打印出来，就可以很明显发现哪里出问题了。

每次选择节点后，minDist数组的变化是否符合预期，是否和我上面讲的逻辑是对应的。

例如本题，如果想debug的话，打印日志可以这样写：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;}int start = 1;int end = n;std::vector<int> minDist(n + 1, INT_MAX);std::vector<bool> visited(n + 1, false);minDist[start] = 0;for (int i = 1; i <= n; i++) {int minVal = INT_MAX;int cur = 1;for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}visited[cur] = true;for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}// 打印日志：cout << "select:" << cur << endl;for (int v = 1; v <= n; v++) cout <<  v << ":" << minDist[v] << " ";cout << endl << endl;;}if (minDist[end] == INT_MAX) cout << -1 << endl;else cout << minDist[end] << endl;}

打印后的结果：

select:1
1:0 2:1 3:4 4:2147483647 5:2147483647 6:2147483647 7:2147483647select:2
1:0 2:1 3:3 4:6 5:2147483647 6:5 7:2147483647select:3
1:0 2:1 3:3 4:5 5:2147483647 6:5 7:2147483647select:4
1:0 2:1 3:3 4:5 5:8 6:5 7:2147483647select:6
1:0 2:1 3:3 4:5 5:8 6:5 7:14select:5
1:0 2:1 3:3 4:5 5:8 6:5 7:12select:7
1:0 2:1 3:3 4:5 5:8 6:5 7:12

打印日志可以和上面我讲解的过程进行对比，每一步的结果是完全对应的。

所以如果大家如果代码有问题，打日志来debug是最好的方法

如何求路径

如果题目要求把最短路的路径打印出来，应该怎么办呢？

这里还是有一些“坑”的，本题打印路径和 prim 打印路径是一样的，我在 prim算法精讲【拓展】中已经详细讲解了。

在这里就不再赘述。

打印路径只需要添加几行代码，打印路径的代码我都加上的日志，如下：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;}int start = 1;int end = n;std::vector<int> minDist(n + 1, INT_MAX);std::vector<bool> visited(n + 1, false);minDist[start] = 0;//加上初始化vector<int> parent(n + 1, -1);for (int i = 1; i <= n; i++) {int minVal = INT_MAX;int cur = 1;for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}visited[cur] = true;for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];parent[v] = cur; // 记录边}}}// 输出最短情况for (int i = 1; i <= n; i++) {cout << parent[i] << "->" << i << endl;}
}

打印结果：

-1->1
1->2
2->3
3->4
4->5
2->6
5->7

对应如图：

出现负数

如果图中边的权值为负数，dijkstra 还合适吗？

看一下这个图：（有负权值）

节点1 到节点5 的最短路径应该是节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5

那我们来看dijkstra 求解的路径是什么样的，继续dijkstra 三部曲来模拟：（dijkstra模拟过程上面已经详细讲过，以下只模拟重要过程，例如如何初始化就省略讲解了）

初始化：

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

更新 minDist数组，即：源点（节点1）到节点2 和节点3的距离。

源点到节点2的最短距离为100，小于原minDist[2]的数值max，更新minDist[2] = 100
源点到节点3的最短距离为1，小于原minDist[3]的数值max，更新minDist[4] = 1

1、选源点到哪个节点近且该节点未被访问过

源点距离节点3最近，距离为1，且未被访问。

2、该最近节点被标记访问过

标记节点3访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点3的加入，那么源点可以有新的路径链接到节点4 所以更新minDist数组：

源点到节点4的最短距离为2，小于原minDist[4]的数值max，更新minDist[4] = 2

1、选源点到哪个节点近且该节点未被访问过

源点距离节点4最近，距离为2，且未被访问。

2、该最近节点被标记访问过

标记节点4访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点4的加入，那么源点可以有新的路径链接到节点5 所以更新minDist数组：

源点到节点5的最短距离为3，小于原minDist[5]的数值max，更新minDist[5] = 5

1、选源点到哪个节点近且该节点未被访问过

源点距离节点5最近，距离为3，且未被访问。

2、该最近节点被标记访问过

标记节点5访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

节点5的加入，而节点5 没有链接其他节点，所以不用更新minDist数组，仅标记节点5被访问过了

1、选源点到哪个节点近且该节点未被访问过

源点距离节点2最近，距离为100，且未被访问。

2、该最近节点被标记访问过

标记节点2访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

至此dijkstra的模拟过程就结束了，根据最后的minDist数组，我们求节点1 到节点5 的最短路径的权值总和为 3，路径：节点1 -> 节点3 -> 节点4 -> 节点5

通过以上的过程模拟，我们可以发现之所以没有走有负权值的最短路径是因为在访问节点 2 的时候，节点 3 已经访问过了，就不会再更新了。

那有录友可能会想：我可以改代码逻辑啊，访问过的节点，也让它继续访问不就好了？

那么访问过的节点还能继续访问会不会有死循环的出现呢？控制逻辑不让其死循环？那特殊情况自己能都想清楚吗？（可以试试，实践出真知）

对于负权值的出现，大家可以针对某一个场景不断去修改 dijkstra 的代码，但最终会发现只是拆了东墙补西墙，对dijkstra的补充逻辑只能满足某特定场景最短路求解。

对于求解带有负权值的最短路问题，可以使用 Bellman-Ford 算法，我在后序会详细讲解。

dijkstra与prim算法的区别

这里再次提示，需要先看我的 prim算法精讲，否则可能不知道我下面讲的是什么。

大家可以发现 dijkstra的代码看上去怎么和 prim算法这么像呢。

其实代码大体不差，唯一区别在三部曲中的第三步：更新minDist数组

因为prim是求非访问节点到最小生成树的最小距离，而 dijkstra是求非访问节点到源点的最小距离。

prim 更新 minDist数组的写法：

for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}
}

因为 minDist表示节点到最小生成树的最小距离，所以新节点cur的加入，只需要使用 grid[cur][j] ，grid[cur][j] 就表示 cur 加入生成树后，生成树到节点j 的距离。

dijkstra 更新 minDist数组的写法：

for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}
}

因为 minDist表示节点到源点的最小距离，所以新节点 cur 的加入，需要使用源点到cur的距离（minDist[cur]） + cur 到节点 v 的距离（grid[cur][v]），才是源点到节点v的距离。

此时大家可能不禁要想 prim算法可以有负权值吗？

当然可以！

录友们可以自己思考思考一下，这是为什么？

这里我提示一下：prim算法只需要将节点以最小权值和链接在一起，不涉及到单一路径。