DijkstraDijkstra

持续确定当前距离最小的顶点并松弛相邻边。

核心约束: 已确定的最短距离不会被后续路径改善。
适用问题: 非负边权最短路。
边界与取舍: 不适用于一般负权边；堆与图表示影响成本。

时间与空间#

V 为顶点数，E 为边数；使用邻接表和索引二叉最小堆。

时间复杂度: $O((V + E)\log V)$
辅助空间: 索引堆 $O(V)$ ；重复入堆版可 $O(V+E)$

边权非负，数值加法与比较无溢出。用 decrease-key 保持每顶点一个堆项；懒删除版会保存多个候选。邻接矩阵配合线性选点为 $O(V^{2})$ 。

基础原理参考资料

Princeton · DijkstraSP非负权条件、索引最小堆实现及数值限制。