Dijkstra 算法（迪杰斯特拉算法）
Dijkstra 算法用于求解单源最短路径问题（Single-Source Shortest Path, SSSP），即给定一个带权有向图 G = (V, E) 和一个源点 s，求从 s 到图中其余各顶点的最短路径。
算法基本思想
Dijkstra 算法采用贪心策略。维护一个集合 S，存放已求出最短路径的顶点。初始时 S 中只包含源点 s，然后重复执行以下步骤：
- 从未确定最短路径的顶点集合 V - S 中，选取一个距离源点最近的顶点 v 加入 S
- 以 v 作为中间顶点，更新从源点到其他未确定顶点的最短路径距离
辅助数组
算法需要维护以下三个辅助数组：
- dist[v]：当前从源点到顶点 v 的最短路径长度
- path[v]：最短路径中 v 的前驱顶点，用于回溯得到完整的路径
- selected[v]：标记顶点 v 是否已加入 S 集合
算法步骤
- 初始化：将源点 s 加入 S 集合，dist[s] = 0；对于其他顶点 v，若存在边 (s, v)，则 dist[v] = w(s, v)，否则 dist[v] = INF
- 循环 n - 1 次（n 为顶点个数）：
- 从 V - S 中选择 dist 值最小的顶点 v，将其加入 S
- 对于 v 的每个邻接顶点 u（u 不在 S 中），若 dist[v] + w(v, u) < dist[u]，则更新 dist[u] = dist[v] + w(v, u)，并设置 path[u] = v
复杂度分析
- 时间复杂度：O(|V|^2)，其中 |V| 是顶点个数。若使用优先队列（堆）优化，可以降至 O((|V| + |E|) log |V|)
- 空间复杂度：O(|V|)
局限性
- 不适用于含有负权边的图。Dijkstra 算法基于贪心思想，一旦某个顶点被加入 S 集合，其 dist 值即视为最终最短路径，不会再次更新。如果存在负权边，之后可能出现更短的路径，导致算法失效。
- 对于含有负权边的图，应使用 Bellman-Ford 算法或 SPFA 算法。
- Dijkstra 算法同样适用于无向带权图。
链接到
- 上一个知识点：7.10 关键路径
- 下一个知识点：7.12 Floyd算法