一文彻底搞懂DIJKSTRA算法（迪杰斯特拉算法）
1. 算法本质
Dijkstra算法 是解决非负权图单源最短路径的经典贪心算法。
由荷兰计算机科学家 Edsger W. Dijkstra 于1956年提出。
核心思想：按路径长度递增的顺序，逐步确定从源点到其余各顶点的最短路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 适用场景与前提
* 适用：带权有向图或无向图，边权 ≥ 0。
* 不适用：含负权边的图（此时应使用 Bellman-Ford 或 SPFA）。
* 目标：求给定源点 s 到所有其他顶点的最短距离。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 核心数据结构
* dist[]：记录源点到每个顶点的当前最短距离估计值，初始化 dist[s]=0，其余为 ∞。
* visited[]（或 settled[]）：标记顶点是否已确定最短距离（永久标号）。
* 优先队列（小顶堆）：快速取出当前 dist 最小的未确定顶点，优化时间复杂度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 算法步骤（手动模拟版）
1. 初始化：dist[s]=0，其余 dist=∞，所有顶点未访问。
2. 从未访问顶点中选择 dist 最小的顶点 u（初始为源点）。
3. 标记 u 为已访问（确定其最短距离）。
4. 松弛操作：遍历 u 的所有邻接边 (u, v, w)，若 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w。
5. 重复步骤 2~4，直到所有顶点被访问或剩余 dist 全为 ∞（非连通图）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 图解示例（手动推演）
图：
顶点：A(源点), B, C, D
边：A-B(4), A-C(2), B-C(1), B-D(5), C-D(8)
步骤 已确定顶点 dist[A] dist[B] dist[C] dist[D] 选择 初始 无 0 ∞ ∞ ∞ A 1 A 0 4 2 ∞ C 2 A,C 0 3(4→2+1) 2 10(2+8) B 3 A,C,B 0 3 2 8(3+5) D 结束 全部 0 3 2 8 -
最终最短路径：
A→C(2), A→B(3) [A→C→B], A→D(8) [A→C→B→D]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 代码实现（PYTHON + 堆优化）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 复杂度分析
实现方式 时间复杂度 空间复杂度 邻接矩阵 + 朴素 O(V²) O(V²) 邻接表 + 二叉堆 O((V+E) log V) O(V+E) 邻接表 + 斐波那契堆 O(E + V log V) O(V+E)
> V：顶点数，E：边数。优先队列堆优化是实际中最常用方式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 正确性证明（简要）
* 不变式：每次从 visited 中取出的顶点 u，其 dist[u] 已是全局最小值。
* 反证法：若存在更短路径到达 u，则该路径上第一个未访问顶点 x 的 dist[x] 必小于 dist[u]，与 u 是当前最小矛盾。
* 由于所有边权非负，后续路径不可能使 dist[u] 更小，故贪心选择安全。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 常见误区与注意事项
* 不能处理负权边：负权会使贪心失效（可能绕负权环减小距离）。
* 不一定适用于所有最短路变种：如求最长路、含负权图、多源最短路等。
* 图必须连通吗？ 不必须，非连通部分距离保持 ∞。
* 堆中可能出现旧数据：用 visited 或比较 d == dist[u] 来跳过过期条目。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 路径还原（附加）
若需要输出具体最短路径，维护 parent[] 数组，在松弛时记录 parent[v] = u，最后反向追溯。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 总结
特点 说明 算法类型 贪心算法 适用图 非负权有向图/无向图 时间复杂度 O((V+E) log V)（堆优化） 空间复杂度 O(V+E) 稳定性 稳定，无负权环时必得正确解 典型应用 地图导航、网络路由、任务调度等
一句话记忆：
> 每次从「未确定」的顶点中挑一个「当前最近」的，然后用它去「松弛」邻居，直到所有顶点都确定下来。
