Dijkstra 算法
经典的最短路径算法，适用于非负权重图，基于贪心思想，使用优先级队列优化。
核心思想
Dijkstra 算法用于求解单源最短路径问题（从一个源点到其他所有点的最短路径）。
算法特点：
- 基于贪心思想：每次选择当前距离源点最近的未访问节点
- 使用优先级队列（最小堆）动态获取当前最近节点，时间复杂度 O(E log V)
- 只适用于非负权重边（边权重 ≥ 0），若存在负权重边需要使用 Bellman-Ford 算法
与 Prim 算法的关系
Dijkstra 算法是 Prim 算法 的基础。Prim 算法用于求解最小生成树问题，其核心步骤可以由 Dijkstra 算法拓展而来：
- Dijkstra：维护「源点到各点的当前最短距离」
- Prim：维护「已选节点集合到各未选节点的当前最小权重」
两者都使用优先级队列，但 Prim 算法关注的是"连接已选集合的最小权重边"。
应用场景
- 地图导航（两点间最短路径）
- 网络路由协议（OSPF 等）
- 游戏 AI 寻路（常与 A* 算法对比使用）
相关算法对比
| 算法 | 适用场景 | 负权重边 | 时间复杂度 |
|---|---|---|---|
| Dijkstra | 单源最短路径 | ❌ 不支持 | O(E log V) |
| Bellman-Ford | 单源最短路径 | ✅ 支持 | O(VE) |
| A* | 点对点最短路径（启发式） | ❌ 不支持 | O(E log V) |
| Floyd | 多源最短路径 | ✅ 支持 | O(V³) |