Appearance
Dijkstra 算法
加权图的单源最短路径
打开手机导航，输入目的地，几毫秒内就能算出最优路线——底层跑的就是 Dijkstra 的变体。这个 1956 年由荷兰计算机科学家 Dijkstra 在咖啡馆里用 20 分钟想出来的算法，至今仍是路径规划的基石。
Dijkstra 算法是解决带权有向图（权值非负） 单源最短路径问题的经典算法，也是 408 考研图论章节的核心考点之一。理解 Dijkstra 算法，也是学习 Floyd 等其他最短路径算法的基础。
核心思想
Dijkstra 算法采用贪心策略：每一轮从尚未确定最短路径的顶点中，选出距离源点最近的顶点，将其最短路径确定下来，然后用该顶点去松弛（更新）与它相邻的顶点的距离。
算法维护两个关键数组：
dist[]：记录源点到各顶点的当前最短距离估计值，初始时源点为 0，其余为 ∞visited[]：标记顶点的最短路径是否已确定，初始全部为falsepath[]：记录最短路径上各顶点的前驱，path[v]表示源点到 v 的最短路径上 v 的前一个顶点，用于回溯完整路径
核心操作——松弛（Relaxation）：
若 dist[u] + w(u,v) < dist[v]，则更新 dist[v] = dist[u] + w(u,v)即：经过顶点 u 到达 v 的路径比当前已知路径更短时，就更新 v 的最短距离。
交互可视化
通过下方的交互动画，你可以逐步观察Dijkstra 算法的执行过程：
操作详解
算法思路
- 初始化：
dist[src] = 0，其余dist[i] = ∞；visited[]全部置false - 重复以下步骤 V 次（V 为顶点数）：
- 从未访问的顶点中选出
dist值最小的顶点 u，标记visited[u] = true - 对 u 的所有邻接顶点 v 执行松弛操作：若
dist[u] + w(u,v) < dist[v]，则更新dist[v]
- 从未访问的顶点中选出
- 算法结束后，
dist[]中即为源点到各顶点的最短路径长度
C/C++ 实现（邻接矩阵版）：
c
#define INF 0x3f3f3f3f
#define MAX_V 100
int graph[MAX_V][MAX_V]; // 邻接矩阵，graph[i][j] 表示边权
int dist[MAX_V]; // 源点到各顶点的最短距离
bool visited[MAX_V]; // 是否已确定最短路径
int path[MAX_V]; // 最短路径上各顶点的前驱
void dijkstra(int n, int src) {
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = false;
path[i] = -1;
}
dist[src] = 0;
path[src] = src;
for (int i = 0; i < n; i++) {
// 选出未访问顶点中 dist 最小的顶点 u
int u = -1, minDist = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) break; // 剩余顶点不可达
visited[u] = true;
// 用 u 松弛其邻接顶点
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != INF
&& dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
path[v] = u;
}
}
}
}执行过程详解
以下图为例，求从顶点 0 出发到其余各顶点的最短路径：
1
0 ----→ 1
| / \
4 | 2/ \6
↓ ↙ ↓
2 ----→ 3
3逐步执行过程：
第 1 轮：选中 u = 0（dist[0]=0 最小）
- 标记 visited[0] = true
- 松弛 0→1：dist[0]+1 = 1 < ∞ = dist[1]，更新 dist[1] = 1
- 松弛 0→2：dist[0]+4 = 4 < ∞ = dist[2]，更新 dist[2] = 4
- 当前 dist = [0, 1, 4, ∞]
第 2 轮：选中 u = 1（未访问中 dist[1]=1 最小）
- 标记 visited[1] = true
- 松弛 1→2：dist[1]+2 = 3 < 4 = dist[2]，更新 dist[2] = 3
- 松弛 1→3：dist[1]+6 = 7 < ∞ = dist[3]，更新 dist[3] = 7
- 当前 dist = [0, 1, 3, 7]
第 3 轮：选中 u = 2（未访问中 dist[2]=3 最小）
- 标记 visited[2] = true
- 松弛 2→3：dist[2]+3 = 6 < 7 = dist[3]，更新 dist[3] = 6
- 当前 dist = [0, 1, 3, 6]
第 4 轮：选中 u = 3（唯一未访问顶点）
- 标记 visited[3] = true
- 顶点 3 无出边，无松弛操作
- 最终 dist = [0, 1, 3, 6]
易错：每轮选中的顶点一旦标记 visited，其 dist 值就不会再改变。如果考试中你发现后续轮次又更新了已访问顶点的 dist，说明你的模拟过程有误。
汇总表格：
| 轮次 | 选中顶点 u | dist[0] | dist[1] | dist[2] | dist[3] | 说明 |
|---|---|---|---|---|---|---|
| 初始 | — | 0 | ∞ | ∞ | ∞ | 源点距离为 0 |
| 1 | 0 | 0 | 1 | 4 | ∞ | 松弛 0→1(1), 0→2(4) |
| 2 | 1 | 0 | 1 | 3 | 7 | 松弛 1→2(1+2=3), 1→3(1+6=7) |
| 3 | 2 | 0 | 1 | 3 | 6 | 松弛 2→3(3+3=6) |
| 4 | 3 | 0 | 1 | 3 | 6 | 全部确定 |
加粗表示该顶点最短路径已确定（visited = true）。
路径回溯
dist[] 只记录了最短距离，要还原完整路径需要 path[] 数组。从终点逆着 path[] 往回走，直到回到源点：
c
// 打印从 src 到 dest 的最短路径
void printPath(int path[], int dest) {
if (path[dest] == dest) { // 到达源点
printf("%d", dest);
return;
}
printPath(path, path[dest]); // 先打印前面的路径
printf(" → %d", dest);
}沿用上面的例子，path[] 数组的变化：
| 轮次 | path[0] | path[1] | path[2] | path[3] |
|---|---|---|---|---|
| 初始 | 0 | -1 | -1 | -1 |
| 1 | 0 | 0 | 0 | -1 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 0 | 1 | 2 |
| 4 | 0 | 0 | 1 | 2 |
回溯 0→3 的最短路径：path[3]=2 → path[2]=1 → path[1]=0（源点），反过来就是 0→1→2→3，路径长度 = dist[3] = 6。
⚠️ 易错：408 大题经常要求"写出最短路径"而不仅是"求最短距离"。只维护
dist[]而不维护path[]会导致无法回答路径问题。手算 Dijkstra 时建议同时维护两个数组。
负权边的局限性
Dijkstra 算法不能处理含负权边的图。原因在于贪心策略的前提假设：一旦某顶点被标记为已访问，其 dist 值就是最终最短距离。但在存在负权边时，后续可能通过负权边找到更短的路径，违反了这一假设。
反例： 0 --5-→ 1 --(-3)-→ 2
0 --3-→ 2
Dijkstra 先确定 dist[2] = 3，但实际 0→1→2 = 5+(-3) = 2 更短。对于含负权边（无负权回路）的图，应使用 Bellman-Ford 算法。
易错：Dijkstra 不能处理负权边，但 可以处理带 0 权边的图。408 选择题中"负权"和"非正权"是不同概念，注意区分。
复杂度分析
| 实现方式 | 时间复杂度 | 适用场景 |
|---|---|---|
| 邻接矩阵 + 简单遍历 | O(V²) | 稠密图 |
| 邻接表 + 最小堆（优先队列） | O(E log V) | 稀疏图 |
选择依据：当 E 远小于 V² 时（稀疏图），使用堆优化更高效；当 E 接近 V²（稠密图），朴素实现反而更优。
| 指标 | 朴素实现 | 堆优化实现 |
|---|---|---|
| 时间复杂度 | O(V²) | O(E log V) |
| 空间复杂度 | O(V²)（邻接矩阵） | O(V + E)（邻接表 + 堆） |
易错：408 常考"对所有顶点分别执行 Dijkstra"与"直接用 Floyd"的时间复杂度对比——两者都是 O(V³)（邻接矩阵实现），但 Floyd 代码更简洁，且能处理负权边。
与 Floyd 算法对比：
| 对比项 | Dijkstra | Floyd |
|---|---|---|
| 问题类型 | 单源最短路径 | 多源（所有顶点对）最短路径 |
| 时间复杂度 | O(V²) / O(E log V) | O(V³) |
| 负权边 | 不支持 | 支持（不能有负权回路） |
| 算法思想 | 贪心 | 动态规划 |
| 适用场景 | 求某一点到其余各点的最短路径 | 求任意两点间的最短路径 |
考研高频考点
- ⭐ 手动模拟 Dijkstra 执行过程，填写 dist[] 表格（选择题/填空题高频）
- ⭐ Dijkstra 不能处理负权边的原因（简答题/判断题必考）
- ⭐ 时间复杂度 O(V²) 与堆优化 O(E log V) 的区别与适用场景
- ⭐ Dijkstra vs Floyd 的对比（简答题高频）
- 贪心策略的正确性理解（为什么每次选最小的 dist 是安全的）
- 松弛操作的含义与实现
- ⭐ path[] 数组记录前驱、回溯完整路径的方法（大题常考"写出最短路径"）
相关知识
- Dijkstra 的堆优化本质上是用**最小堆（优先队列）**维护 dist[] 中的最小值，参见堆排序中建堆与调整的过程
- 求所有顶点对之间的最短路径，使用 Floyd 算法更直接——三重循环，代码仅 5 行
- Dijkstra 的松弛操作与 BFS 最短路径的思想一脉相承：BFS 适用于无权图（边权全为 1），Dijkstra 是其在带权图上的推广
- 负权边场景需要 Bellman-Ford 算法，408 一般不要求实现，但需要知道 Dijkstra 的局限性