定义
Dijkstra 算法（迪杰斯特拉算法）是求解单源最短路径问题的经典算法，由荷兰计算机科学家 Dijkstra 提出。
适用条件
- 带权有向图或无向图
- 边权必须非负
算法思想
- 初始化：源点距离为 0，其他顶点距离为 ∞
- 选择距离最小的未确定顶点 u，标记为已确定
- 对 u 的所有邻接顶点 v 进行松弛操作：若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]
- 重复步骤 2-3，直到所有顶点都确定
时间复杂度
- 邻接矩阵 + 线性搜索：
- 邻接表 + 优先队列：
与 Floyd 算法对比
| 算法 | 问题 | 时间复杂度 |
|---|---|---|
| Dijkstra | 单源最短路径 | 或 |
| Floyd | 所有顶点对最短路径 |