## C++ 基础讲义：最短路径问题——Dijkstra 算法本节主要学习： 1. 单源最短路； 2. Dijkstra 算法思想； 3. Dijkstra 的适用条件； 4. 朴素 Dijkstra； 5. 堆优化 Dijkstra； 6. 优先队列在 Dijkstra 中的作用； 7. 常见错误。 --- ## 一、什么是单源最短路单源最短路是指： ```text 从一个固定起点出发，求它到图中所有点的最短距离。 ``` 例如： ```text 起点是 1。求 1 到 2、1 到 3、1 到 4 ... 的最短距离。 ``` 上一节讲的 Floyd 是多源最短路： ```text 求任意两点之间的最短距离。 ``` 而 Dijkstra 是单源最短路： ```text 只从一个起点出发。 ``` --- ## 二、Dijkstra 算法思想 Dijkstra 的核心思想是： ```text 每次从还没有确定最短距离的点中，选出当前距离起点最近的点，然后用这个点去更新其他点。 ``` 可以理解为： ```text 先确定离起点最近的点。再用这个点扩展更远的点。不断重复，直到所有点都确定。 ``` --- ## 三、Dijkstra 的适用条件 Dijkstra 只能用于： ```text 边权非负的图。 ``` 也就是说，边的权值不能是负数。如果边权有负数，Dijkstra 可能出错。原因是： ```text Dijkstra 认为一旦某个点的最短距离确定，就不会再改变。但如果有负权边，已经确定的点可能又被更新得更小。 ``` 如果图中有负权边，需要使用： ```text Bellman-Ford SPFA ``` --- ## 四、Dijkstra 中的数组朴素 Dijkstra 通常使用三个数组。 ### 1. dist 数组 ```cpp dist[i] ``` 表示： ```text 当前从起点到点 i 的最短距离估计值。 ``` 初始时： ```cpp dist[start] = 0 ``` 其他点： ```cpp dist[i] = INF ``` --- ### 2. vis 数组 ```cpp vis[i] ``` 表示： ```text 点 i 的最短距离是否已经确定。 ``` 如果： ```cpp vis[i] == true ``` 说明点 `i` 的最短距离已经确定。 --- ### 3. 图的存储朴素 Dijkstra 常用邻接矩阵： ```cpp g[u][v] ``` 表示： ```text 从 u 到 v 的边权。 ``` 如果没有边： ```cpp g[u][v] = INF ``` --- ## 五、朴素 Dijkstra 的基本过程假设起点是： ```text start ``` 步骤如下： ```text 1. 初始化 dist[start] = 0，其他点为 INF。 2. 重复 n 次：找一个还没有确定最短距离、且 dist 最小的点 u。把 u 标记为已确定。用 u 更新它的所有相邻点 v。 ``` 更新公式： ```cpp if (dist[u] + g[u][v] < dist[v]) { dist[v] = dist[u] + g[u][v]; } ``` 含义： ```text 如果经过 u 到 v 更近，就更新 v 的最短距离。 ``` --- ## 六、朴素 Dijkstra 示例有 `4` 个点： ```text 1 -> 2，权值 1 1 -> 3，权值 5 2 -> 3，权值 2 3 -> 4，权值 1 ``` 起点是： ```text 1 ``` 初始： ```text dist[1] = 0 dist[2] = INF dist[3] = INF dist[4] = INF ``` --- ### 第一步未确定的点中，距离最小的是： ```text 1 ``` 确定点 `1`。用点 `1` 更新： ```text 1 -> 2，权值 1 1 -> 3，权值 5 ``` 得到： ```text dist[2] = 1 dist[3] = 5 ``` --- ### 第二步未确定的点中，距离最小的是： ```text 2 ``` 确定点 `2`。用点 `2` 更新： ```text 2 -> 3，权值 2 ``` 原来： ```text dist[3] = 5 ``` 经过点 `2`： ```text dist[2] + 2 = 1 + 2 = 3 ``` 更新： ```text dist[3] = 3 ``` --- ### 第三步未确定的点中，距离最小的是： ```text 3 ``` 确定点 `3`。用点 `3` 更新： ```text 3 -> 4，权值 1 ``` 得到： ```text dist[4] = 3 + 1 = 4 ``` --- ### 第四步未确定的点中，距离最小的是： ```text 4 ``` 确定点 `4`。最终： ```text dist[1] = 0 dist[2] = 1 dist[3] = 3 dist[4] = 4 ``` --- ## 七、朴素 Dijkstra 完整代码 ```cpp #include using namespace std; const int N = 1005; // 最大点数 const long long INF = 1e18; // 一个很大的数，表示不可达 long long g[N][N]; // 邻接矩阵，g[u][v] 表示边权 long long dist[N]; // dist[i] 表示起点到 i 的最短距离 bool vis[N]; // vis[i] 表示 i 的最短距离是否已经确定 int n, m; // n 个点，m 条边 int start; // 起点 int main() { cin >> n >> m >> start; // 输入点数、边数、起点 for (int i = 1; i <= n; i++) { // 初始化邻接矩阵 for (int j = 1; j <= n; j++) { if (i == j) { g[i][j] = 0; } else { g[i][j] = INF; } } } for (int i = 1; i <= m; i++) { // 读入边 int u, v; long long w; cin >> u >> v >> w; // 输入 u -> v，权值 w if (w < g[u][v]) { // 如果有重边，保留最小边 g[u][v] = w; } } for (int i = 1; i <= n; i++) { // 初始化 dist dist[i] = INF; vis[i] = false; } dist[start] = 0; // 起点到起点距离为 0 for (int t = 1; t <= n; t++) { // 最多确定 n 个点 int u = -1; // 当前要找的未确定点 for (int i = 1; i <= n; i++) { // 找 dist 最小的未确定点 if (!vis[i] && (u == -1 || dist[i] < dist[u])) { u = i; } } if (u == -1 || dist[u] == INF) { // 剩余点不可达 break; } vis[u] = true; // 确定 u 的最短距离 for (int v = 1; v <= n; v++) { // 用 u 更新其他点 if (!vis[v] && g[u][v] != INF) { // v 未确定，且 u 到 v 有边 if (dist[u] + g[u][v] < dist[v]) { dist[v] = dist[u] + g[u][v]; // 更新最短距离 } } } } for (int i = 1; i <= n; i++) { // 输出起点到每个点的距离 if (dist[i] == INF) { cout << start << " 到 " << i << " 不可达" << '\n'; } else { cout << start << " 到 " << i << " 的最短距离是 " << dist[i] << '\n'; } } return 0; } ``` 如果输入： ```text 4 4 1 1 2 1 1 3 5 2 3 2 3 4 1 ``` 输出： ```text 1 到 1 的最短距离是 0 1 到 2 的最短距离是 1 1 到 3 的最短距离是 3 1 到 4 的最短距离是 4 ``` --- ## 八、朴素 Dijkstra 的时间复杂度朴素 Dijkstra 中，每次要找最小距离的点： ```text O(n) ``` 一共找 `n` 次： ```text O(n^2) ``` 更新边也可能花费： ```text O(n^2) ``` 所以总时间复杂度约为： ```text O(n^2) ``` 适合： ```text 点数较少，边较多的稠密图。 ``` 如果点数很大，例如： ```text n = 100000 ``` 朴素 Dijkstra 会太慢。这时需要使用堆优化 Dijkstra。 --- ## 九、堆优化 Dijkstra 思想朴素 Dijkstra 每次都要遍历所有点，找距离最小的点。这一步可以用优先队列优化。优先队列可以自动取出当前距离最小的点。基本思想： ```text 把点按照当前 dist 放入优先队列。每次取出距离最小的点。如果这个点的距离已经被更新过，就跳过。否则用它更新相邻点。 ``` --- ## 十、优先队列中保存什么优先队列中通常保存： ```cpp pair<距离, 点编号> ``` 例如： ```cpp pair ``` 其中： ```text first 是当前距离 second 是点编号 ``` 默认优先队列是大根堆。 Dijkstra 需要每次取出距离最小的点，所以要用小根堆： ```cpp priority_queue< pair, vector>, greater> > pq; ``` --- ## 十一、堆优化 Dijkstra 代码这里使用链式前向星存图。 ```cpp #include #include #include #include #include using namespace std; const int N = 100000 + 5; // 最大点数 const int M = 200000 + 5; // 最大边数 const long long INF = 1e18; // 不可达 int head[N]; // 每个点的第一条边 int to[M]; // 边指向的点 int nxt[M]; // 下一条边 long long w[M]; // 边权 int cnt = 0; // 边数 int n, m, start; // 点数、边数、起点 long long dist[N]; // 最短距离 bool vis[N]; // 是否已经处理过 void init() { // 初始化链式前向星 for (int i = 1; i <= n; i++) { head[i] = -1; } cnt = 0; } void add(int u, int v, long long weight) { // 加入有向边 cnt++; to[cnt] = v; w[cnt] = weight; nxt[cnt] = head[u]; head[u] = cnt; } void dijkstra(int s) { // 堆优化 Dijkstra for (int i = 1; i <= n; i++) { // 初始化 dist[i] = INF; vis[i] = false; } priority_queue< pair, vector>, greater> > pq; // 小根堆 dist[s] = 0; // 起点距离为 0 pq.push({0, s}); // 起点入队 while (!pq.empty()) { // 队列不为空 pair cur = pq.top(); // 取出队首 pq.pop(); // 删除队首 long long d = cur.first; // 当前距离 int u = cur.second; // 当前点 if (d != dist[u]) { // 过期信息，跳过 continue; } if (vis[u]) { // 已经处理过 continue; } vis[u] = true; // 标记为已处理 for (int i = head[u]; i != -1; i = nxt[i]) { // 遍历 u 的出边 int v = to[i]; // 边指向的点 long long weight = w[i]; // 边权 if (dist[v] > dist[u] + weight) { // 发现更短路径 dist[v] = dist[u] + weight; // 更新距离 pq.push({dist[v], v}); // 加入优先队列 } } } } int main() { cin >> n >> m >> start; // 输入点数、边数、起点 init(); // 初始化 for (int i = 1; i <= m; i++) { // 读入边 int u, v; long long weight; cin >> u >> v >> weight; // 输入 u -> v，权值 weight add(u, v, weight); // 有向图 } dijkstra(start); // 从起点开始最短路 for (int i = 1; i <= n; i++) { // 输出结果 if (dist[i] == INF) { cout << start << " 到 " << i << " 不可达" << '\n'; } else { cout << start << " 到 " << i << " 的最短距离是 " << dist[i] << '\n'; } } return 0; } ``` 如果输入： ```text 4 4 1 1 2 1 1 3 5 2 3 2 3 4 1 ``` 输出： ```text 1 到 1 的最短距离是 0 1 到 2 的最短距离是 1 1 到 3 的最短距离是 3 1 到 4 的最短距离是 4 ``` --- ## 十二、堆优化 Dijkstra 中的过期信息在堆优化 Dijkstra 中，同一个点可能多次进入优先队列。例如点 `v` 的距离先是： ```text 10 ``` 后来被更新为： ```text 6 ``` 那么优先队列里可能同时有： ```text (10, v) (6, v) ``` 当取出： ```text (10, v) ``` 时，这个信息已经过期。所以要判断： ```cpp if (d != dist[u]) { continue; } ``` 或者： ```cpp if (d > dist[u]) { continue; } ``` --- ## 十三、朴素 Dijkstra 和堆优化 Dijkstra 对比 | 写法 | 时间复杂度 | 适合场景 | |---|---|---| | 朴素 Dijkstra | `O(n^2)` | 点数较小，边较多 | | 堆优化 Dijkstra | `O(m log n)` | 点数较大，边较稀疏 | 其中： ```text n 是点数 m 是边数 ``` 初学阶段建议： ```text 先掌握朴素 Dijkstra 的思想。再学习堆优化 Dijkstra 的实现。 ``` --- ## 十四、常见错误 ### 1. 图中有负权边仍然使用 Dijkstra 错误： ```text 边权有负数，但使用 Dijkstra。 ``` 正确： ```text 如果有负权边，使用 Bellman-Ford 或 SPFA。 ``` --- ### 2. k 循环和 Dijkstra 混淆 Floyd 的循环是： ```cpp for k for i for j ``` Dijkstra 不是这样。 Dijkstra 是： ```text 每次选择一个未确定最短距离的最近点。然后用这个点更新其他点。 ``` --- ### 3. 忘记初始化 dist 正确初始化： ```cpp for (int i = 1; i <= n; i++) { dist[i] = INF; } dist[start] = 0; ``` --- ### 4. 优先队列忘记改成小根堆错误： ```cpp priority_queue> pq; ``` 默认是大根堆，会取出距离最大的点。正确： ```cpp priority_queue< pair, vector>, greater> > pq; ``` --- ### 5. 没有跳过过期队列元素错误： ```cpp pair cur = pq.top(); pq.pop(); int u = cur.second; ``` 如果这个元素已经过期，可能会错误处理。正确： ```cpp long long d = cur.first; int u = cur.second; if (d != dist[u]) { continue; } ``` --- ### 6. 无向图忘记加两条边如果题目是无向图： ```cpp add(u, v, w); add(v, u, w); ``` 如果是有向图： ```cpp add(u, v, w); ``` --- ## 十五、小练习 ### 练习 1：朴素 Dijkstra 输入： ```text n m start 接下来 m 条有向边：u v w ``` 输出起点到所有点的最短距离。参考代码： ```cpp #include using namespace std; const int N = 1005; // 最大点数 const long long INF = 1e18; // 不可达 long long g[N][N]; // 邻接矩阵 long long dist[N]; // 最短距离 bool vis[N]; // 是否确定 int n, m, start; // 点数、边数、起点 int main() { cin >> n >> m >> start; for (int i = 1; i <= n; i++) { // 初始化邻接矩阵 for (int j = 1; j <= n; j++) { if (i == j) { g[i][j] = 0; } else { g[i][j] = INF; } } } for (int i = 1; i <= m; i++) { // 读入边 int u, v; long long w; cin >> u >> v >> w; if (w < g[u][v]) { g[u][v] = w; } } for (int i = 1; i <= n; i++) { // 初始化 dist dist[i] = INF; vis[i] = false; } dist[start] = 0; // 起点距离为 0 for (int t = 1; t <= n; t++) { // 确定 n 个点 int u = -1; for (int i = 1; i <= n; i++) { // 找最近的未确定点 if (!vis[i] && (u == -1 || dist[i] < dist[u])) { u = i; } } if (u == -1 || dist[u] == INF) { break; } vis[u] = true; // 确定该点 for (int v = 1; v <= n; v++) { // 更新相邻点 if (!vis[v] && g[u][v] != INF) { if (dist[u] + g[u][v] < dist[v]) { dist[v] = dist[u] + g[u][v]; } } } } for (int i = 1; i <= n; i++) { // 输出结果 if (dist[i] == INF) { cout << "不可达" << '\n'; } else { cout << dist[i] << '\n'; } } return 0; } ``` --- ### 练习 2：堆优化 Dijkstra 输入格式同上。参考代码： ```cpp #include #include #include #include #include using namespace std; const int N = 100000 + 5; // 最大点数 const int M = 200000 + 5; // 最大边数 const long long INF = 1e18; // 不可达 int head[N]; int to[M]; int nxt[M]; long long w[M]; int cnt = 0; int n, m, start; long long dist[N]; bool vis[N]; void init() { // 初始化 for (int i = 1; i <= n; i++) { head[i] = -1; } cnt = 0; } void add(int u, int v, long long weight) { // 加边 cnt++; to[cnt] = v; w[cnt] = weight; nxt[cnt] = head[u]; head[u] = cnt; } void dijkstra(int s) { // 堆优化 Dijkstra for (int i = 1; i <= n; i++) { dist[i] = INF; vis[i] = false; } priority_queue< pair, vector>, greater> > pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { pair cur = pq.top(); pq.pop(); long long d = cur.first; int u = cur.second; if (d != dist[u]) { // 过期信息 continue; } if (vis[u]) { continue; } vis[u] = true; for (int i = head[u]; i != -1; i = nxt[i]) { int v = to[i]; long long weight = w[i]; if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } } int main() { cin >> n >> m >> start; init(); for (int i = 1; i <= m; i++) { int u, v; long long weight; cin >> u >> v >> weight; add(u, v, weight); } dijkstra(start); for (int i = 1; i <= n; i++) { if (dist[i] == INF) { cout << "不可达" << '\n'; } else { cout << dist[i] << '\n'; } } return 0; } ``` --- ## 十六、本节小结本节学习了： ### 1. 单源最短路 ```text 从一个起点出发，求到所有点的最短距离。 ``` --- ### 2. Dijkstra 思想 ```text 每次选择当前距离最小且未确定的点。用它更新其他点。 ``` --- ### 3. 适用条件 ```text 边权必须非负。 ``` --- ### 4. 朴素 Dijkstra ```cpp for (int t = 1; t <= n; t++) { // 找 dist 最小的未确定点 // 标记 // 更新其他点 } ``` 时间复杂度： ```text O(n^2) ``` --- ### 5. 堆优化 Dijkstra ```cpp priority_queue< pair, vector>, greater> > pq; ``` 时间复杂度： ```text O(m log n) ``` ---

09 - Dijkstra算法