Dijkstra（迪杰斯特拉）算法详解：最短路径的贪心求解
Dijkstra 算法可以说是图论中解决最短路径问题的“老朋友”，凡遇到单源最短路径需求，它几乎总是最先被考虑的方法。它的适用条件非常明确：边权非负的图（无论有向还是无向），都能高效地完成单源最短路径的求解。
其核心逻辑其实很简单，就四个字：贪心策略。具体来说，每次从尚未确定最短路径的顶点中，选出当前距离最小的顶点，并将其最短路径视为已确定。接着，以该顶点为中转站，更新其邻居的距离。重复此过程 n-1 轮，即可得到所有顶点的最短路径。
一、算法简介
Dijkstra 算法专用于求解单源最短路径问题，前提是图中所有边的权值非负。其策略简洁明了：每次从尚未确定最短路径的顶点中，选择当前距离最小的顶点，标记为“已确定”。然后利用该顶点更新其未标记邻居的距离，重复直至所有顶点都被确定。
二、辅助数组说明
| 数组 | 作用 |
|---|---|
dist[] | 记录每个顶点到起点的当前最短距离 |
flag[] | 标记顶点是否已确定最短路径（0 未确定，1 已确定） |
pre[] | 记录最短路径中每个顶点的前驱顶点，用于路径回溯 |
三、算法步骤
Step 1 选择起点，初始化其直接可达顶点的距离。
Step 2 在未确定最短路径的顶点中，选择当前距离最小的顶点——该点的最短路径此刻被“锁定”。由于所有边权非负，不可能存在更短路径。
Step 3 以该顶点为中转站，检查其邻接点：若经过该顶点距离更短，则更新距离并记录前驱。
Step 4 重复 Step 2 和 Step 3 共 n-1 次，即可得到所有顶点的最短路径。
四、完整代码实现（邻接矩阵版）
#include五、关键代码分析
5.1 初始化阶段（第 38-46 行）
dist[s] = 0;
flag[s] = 1;
for (int i = 0; i < n; i++)
if (g[s][i] < INF) {
dist[i] = g[s][i];
pre[i] = s;
}
pre[s] = -1;
- 将起点 s 的 dist 设为 0，并标记为已确定。
- 遍历所有顶点，将起点 s 能直接到达的邻接点的
dist初始化为边权值，前驱指向 s。 pre[s] = -1作为路径回溯的终止条件。
5.2 寻找未标记的最小 dist 顶点（第 56-64 行）
k = -1;
minn = INF;
for (int i = 0; i < n; i++)
if (flag[i] == 0 && dist[i] < minn) {
k = i;
minn = dist[i];
}
- 通过线性扫描，在所有未标记顶点中选出
dist最小的顶点。 k = -1作为哨兵值：若循环结束后 k 仍为 -1，说明剩余顶点均不可达（连通性判断）。- 贪心选择正确性：由于边权非负，当前全局最小的
dist[k]不可能再被其他路径缩短，因此 k 的最短路径可以立即确定。
5.3 松弛操作（第 73-79 行）
for (int i = 0; i < n; i++)
if (flag[i] == 0 && dist[k] + g[k][i] < dist[i]) {
dist[i] = dist[k] + g[k][i];
pre[i] = k;
}
- 以 k 为中转点，遍历所有顶点检查能否缩短距离。
- 条件
dist[k] + g[k][i] < dist[i]即为三角不等式的松弛判断。 - 只有未标记的顶点需要更新（已标记的顶点最短路径已确定，不可能更短）。
- 更新
pre[i]记录路径，便于后续回溯输出。
5.4 路径回溯（第 97-102 行）
printf("%d到%d的最短路径长度是%d，其路径为：%d ", s, i, dist[i], i);
int p = pre[i];
while (p != -1) {
printf("%d ", p);
p = pre[p];
}
- 从目标顶点 i 开始，通过
pre[]数组不断回溯到前驱，直到pre[p] == -1（到达起点）。 - 由于是从终点向起点回溯，输出的顶点顺序是反向的（实际路径中 i 在前，起点在最后）。
六、复杂度分析
时间复杂度：O(n²)
- 外层循环：n-1 轮确定 n-1 个顶点。
- 每轮内部执行两次线性扫描：
- 寻找最小 dist：扫描 n 个顶点 → O(n)
- 松弛邻接点：扫描 n 个顶点 → O(n)
- 总复杂度：n × (n + n) = O(n²)
空间复杂度：O(n²)
- 邻接矩阵
g[105][105]占用 O(n²) 空间。 - 辅助数组
dist[]、flag[]、pre[]各占用 O(n)。
当 n 较大（> 10⁴）时，邻接矩阵版将超时或超内存，此时应改用邻接表 + 优先队列优化（堆优化 Dijkstra，复杂度 O((n+m)log n)）。
七、算法特性总结
| 特性 | 说明 |
|---|---|
| 适用范围 | 边权非负的带权图（无向图或有向图） |
| 算法思想 | 贪心：每次取未确定中 dist 最小的顶点 |
| 数据结构 | 邻接矩阵（本实现）或邻接表 + 优先队列 |
| 时间复杂度 | O(n²)（邻接矩阵版）或 O((n+m)log n)（堆优化版） |
| 空间复杂度 | O(n²)（邻接矩阵版） |
| 局限性 | 无法处理负权边（负权边可能导致已确定的 dist 被后续更短的路径违反） |
八、总结
Dijkstra 算法是图论中最基础且应用最广泛的最短路径算法之一。其代码实现简洁清晰，核心逻辑可以概括为三个步骤的循环：
- 选点 — 从未标记的顶点中选出 dist 最小的顶点
- 标记 — 该点最短路径被确定
- 松弛 — 用该点更新邻接点的 dist
掌握 Dijkstra 的思想对于理解更复杂的图论算法（如 A* 搜索、Johnson 全源最短路等）有很大帮助。建议读者在理解原理的基础上，进一步学习堆优化版本以应对大规模图数据。
