Dijkstra 算法
Dijkstra 算法在带权有向图（或无向图）上求解单源最短路：给定源点 ，求到各顶点的最短距离。当边权非负时，算法正确；若存在负权边，需改用 Bellman-Ford 等。
1. 问题与记号
- 图 ，边权 （）。
- 源点 。
- 目标：对所有 ，求 到 的最短路径长度 （或判为不可达）。
基本思想：维护已探索与未探索的划分，每次在未探索顶点中选当前距离最小者作为当前点，对其邻居做距离更新，直到全部处理完毕。以下步骤与标准叙述一致，边权须非负。
2. 算法步骤
初始化
选择一个起始点，将该点作为当前点并将其最短距离标记为 ；将其余所有点的最短距离标记为 ；将所有节点的前一个节点标记为null（或表示“无前驱”的哨兵值）。选当前点
在所有未被探索的节点中，选择最短距离最小的节点作为新的当前点 。松弛邻居
对当前节点 的所有邻居 （即与 相邻的顶点）依次做：将当前节点 的当前最短距离与边 的权相加。若两者之和小于邻居 当前所记录的最短距离，则把 的最短距离更新为该和，并把 的前一个节点更新为当前节点 。标记已探索
将当前节点 标记为已探索。迭代或结束
若图中还存在未被访问的节点，则转向步骤 2；否则算法结束。
3. 实现说明（与优先队列）
上节步骤 2 在顶点很多时，若线性扫描“未被探索中距离最小者”，单步要 ，总复杂度偏高。实现中常用最小堆（优先队列）维护“未探索”顶点及其当前最短距离：步骤 2 对应出堆取最小，步骤 3 的更新对应入堆/松弛后减小键。此时典型的堆操作与边松弛结合，总时间约 ；若使用斐波那契堆等，理论上可至 ，工程中二叉堆更常见。
4. 正确性要点
- 非负权保证：一旦某顶点 以当前最小 dist 从堆中确定，其 dist 即为 ，不会再被缩短。
- 若存在负权边，该性质不成立，Dijkstra 可能错误，应使用 Bellman-Ford 或 Johnson 等。
备忘
（可在此补：与 A*、双向 Dijkstra、动态最短路等。）