本课时有配套视频讲解，购买后即可观看（永久有效）

Dijkstra求单源最短路径

一、课上练习

编程练习

单源最短路径(Dijkstra)：L49977

二、知识总结

✨ 核心思想

Dijkstra 算法用于求解单源最短路径问题：给定一个边权非负的有向图（或无向图），求从源点 $s$ 到所有其他顶点的最短距离。

核心思想是贪心：每次从未确定最短路的顶点中，选择距离源点最近的一个，将其"确定"，然后用它来更新相邻顶点的距离。这种策略之所以正确，是因为边权非负——已确定的最短距离不可能被后续更新变得更小。

✨ 算法原理

初始化：设 dist[s] = 0，其余 dist[v] = ∞。用数组 vis[] 标记已确定最短路的顶点。
重复 $n$ 次：
- 在未确定的顶点中，找到 dist 最小的顶点 $u$ 。
- 将 $u$ 标记为已确定（vis[u] = true）。
- 松弛操作：对于 $u$ 的所有邻居 $v$ ，如果 dist[u] + w(u,v) < dist[v]，则更新 dist[v] = dist[u] + w(u,v)。
当所有顶点都确定后，算法结束。

关键前提：所有边权必须 $\geq 0$ 。如果存在负权边，Dijkstra 可能给出错误结果。

这个版本是朴素实现，每次用 $O(V)$ 遍历找最小值，总时间 $O(V^2)$ 。适用于稠密图（ $E$ 接近 $V^2$ ）。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 5005;
5const int INF = 0x3f3f3f3f;
6
7int g[MAXN][MAXN]; // 邻接矩阵
8int dist[MAXN];    // 源点到各点的最短距离
9bool vis[MAXN];    // 是否已确定最短路
10int n, m, s;       // 顶点数、边数、源点
11
12void dijkstra(int s) {
13    // 初始化距离
14    memset(dist, 0x3f, sizeof(dist));
15    memset(vis, false, sizeof(vis));
16    dist[s] = 0;
17
18    // 重复n次，每次确定一个顶点
19    for (int i = 0; i < n; i++) {
20        // 找到未确定顶点中距离最小的
21        int u = -1;
22        for (int j = 1; j <= n; j++) {
23            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
24                u = j;
25            }
26        }
27
28        if (dist[u] == INF) break; // 剩余顶点不可达
29        vis[u] = true; // 确定u的最短路
30
31        // 用u松弛相邻顶点
32        for (int v = 1; v <= n; v++) {
33            if (!vis[v] && g[u][v] != INF) {
34                if (dist[u] + g[u][v] < dist[v]) {
35                    dist[v] = dist[u] + g[u][v];
36                }
37            }
38        }
39    }
40}
41
42int main() {
43    ios::sync_with_stdio(false);
44    cin.tie(nullptr);
45
46    cin >> n >> m >> s;
47
48    // 初始化邻接矩阵
49    memset(g, 0x3f, sizeof(g));
50    for (int i = 1; i <= n; i++) g[i][i] = 0;
51
52    for (int i = 0; i < m; i++) {
53        int u, v, w;
54        cin >> u >> v >> w;
55        g[u][v] = min(g[u][v], w); // 处理重边，取最小值
56    }
57
58    dijkstra(s);
59
60    // 输出源点到各顶点的最短距离
61    for (int i = 1; i <= n; i++) {
62        if (dist[i] == INF)
63            cout << -1;
64        else
65            cout << dist[i];
66        if (i < n) cout << " ";
67    }
68    cout << endl;
69
70    return 0;
71}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 5005;
5const int INF = 0x3f3f3f3f;
6
7vector<pair<int, int>> adj[MAXN]; // 邻接表：adj[u] = {(v, w), ...}
8int dist[MAXN];
9bool vis[MAXN];
10int n, m, s;
11
12void dijkstra(int s) {
13    memset(dist, 0x3f, sizeof(dist));
14    memset(vis, false, sizeof(vis));
15    dist[s] = 0;
16
17    for (int i = 0; i < n; i++) {
18        int u = -1;
19        for (int j = 1; j <= n; j++) {
20            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
21                u = j;
22            }
23        }
24        if (dist[u] == INF) break;
25        vis[u] = true;
26
27        for (auto [v, w] : adj[u]) {
28            if (!vis[v] && dist[u] + w < dist[v]) {
29                dist[v] = dist[u] + w;
30            }
31        }
32    }
33}
34
35int main() {
36    ios::sync_with_stdio(false);
37    cin.tie(nullptr);
38
39    cin >> n >> m >> s;
40    for (int i = 0; i < m; i++) {
41        int u, v, w;
42        cin >> u >> v >> w;
43        adj[u].push_back({v, w});
44    }
45
46    dijkstra(s);
47
48    for (int i = 1; i <= n; i++) {
49        cout << (dist[i] == INF ? -1 : dist[i]);
50        if (i < n) cout << " ";
51    }
52    cout << endl;
53
54    return 0;
55}

✨ 执行示例

图：5 个顶点，源点 $s = 1$ 。

边：1→2(2), 1→3(5), 2→3(1), 2→4(6), 3→4(3), 3→5(8), 4→5(2)

步骤	选中顶点	dist[2]	dist[3]	dist[4]	dist[5]
初始	-	∞	∞	∞	∞
1	u=1	2	5	∞	∞
2	u=2	2	3	8	∞
3	u=3	2	3	6	11
4	u=4	2	3	6	8
5	u=5	2	3	6	8

最短路径： $1 \to 2$ : 2， $1 \to 3$ : 3， $1 \to 4$ : 6， $1 \to 5$ : 8。

✨ 解题步骤详解

判断是否适用 Dijkstra：确认所有边权非负。有负权边必须用 Bellman-Ford 或 SPFA。
选择存图方式：
- 稠密图（ $E \approx V^2$ ）：邻接矩阵 + 朴素 Dijkstra $O(V^2)$ 。
- 稀疏图（ $E \ll V^2$ ）：邻接表 + 堆优化 Dijkstra $O(E \log V)$ （见下一节）。
处理重边：邻接矩阵取 min，邻接表无需特殊处理。
处理无向图：双向加边即可。
路径输出：若需要输出具体路径，增加 pre[v] 数组记录前驱。

✨ 常见错误

对含负权边的图使用 Dijkstra：这是最严重的错误，会导致结果不正确。
忘记初始化 dist 为 INF：未初始化会导致松弛操作无法正确进行。
邻接矩阵未处理重边：两点间有多条边时，应取权值最小的。
INF 值设置不当：0x3f3f3f3f 约为 $10^9$ ，两个相加不会溢出 int，是常用的 INF 值。
未判断不可达情况：源点无法到达的顶点 dist 仍为 INF，需要特判输出。
稀疏图使用邻接矩阵：当 $V$ 很大（如 $10^5$ ）时，邻接矩阵开不下，应用邻接表。

✨ 算法评价

指标	分析
时间复杂度	$O(V^2)$ ，适合 $V \leq 5000$ 的稠密图
空间复杂度	邻接矩阵 $O(V^2)$ ，邻接表 $O(V + E)$
适用条件	边权非负
优势	实现简单，稠密图效率高
局限	无法处理负权边；稀疏图效率不如堆优化版

朴素 Dijkstra 是最短路径算法的基础，理解其贪心原理对于学习堆优化版和其他最短路算法至关重要。