Dijkstra 算法

Dijkstra 把已结算区看成从源点扩张的距离球。堆中每个键代表一条从球内跨出到该顶点的最佳已知路线；取最小键就是选择下一层边界。由于边权不为负，任何尚未进入球的绕行都不可能先走得更远、再以负代价回来改短已结算点。

松弛负责生成与更新候选，贪心理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。选择负责宣布一个候选不再变化。只做松弛而没有最小键次序，是另一类标签修正算法；只取最小键而不扫描出边，也无法把正确距离传播给后继。

在边

上，结算 $s$ 后暂定 $(d[a],d[b])=(2,5)$；结算 $a$ 后变为 $d[b]=3,d[t]=6$；结算 $b$ 后又把 $d[t]$ 降为 $4$。父指针恢复路径 $s\to a\to b\to t$，其权重 $2+1+1=4$。

负边反例不需要负圈。取

算法先结算 $b$ 并令 $d[t]=3$；等到结算 $a$，真正到 $b$ 的成本才降为 $-1$。标准算法不会重新展开已结算的 $b$，于是返回 $d[t]=3$，而路径 $s\to a\to b\to t$ 的权重是 $1$。这表明非负性是足够且可局部检查的前提；“图中没有负圈”仍不足以使用本算法。

负权图可改用Bellman–Ford 算法理路Bellman–Ford 算法Bellman–Ford algorithm通过反复松弛边求含负权边图的单源最短路并检测可达负环。。零权边和零权圈不破坏正确性，但可能产生多个相同键；平局以任意顺序结算都安全。不可达顶点始终为 $+\mathrm{\infty }$，实现可在最小键已为无穷时停止。平行边逐条松弛即可，同方向只保留最小权边也不改变距离；非负自环不会改进任何估计。

Dijkstra 解决非负权最短路问题理路最短路问题Shortest-path problem在有限有向实权图中寻找源点到各顶点的最小有向游走成本。；图表示理路图的表示Graph representation · Adjacency-list and adjacency-matrix representations依据图的类型与所需操作选择邻接表、邻接矩阵或边集表示的方法。决定能否只扫描现有边，队列实现决定最小键与减键成本。若只查询一个目标 $t$，当 $t$ 被取出并结算时即可停止；在此之前仅仅“发现 $t$”不构成最优性证书。

0–1 BFS理路0–1 BFS0-1 BFS · Zero-one BFS · 零一广度优先搜索对边权仅为零或一的图，用双端队列维持相邻距离层，在严格松弛与旧项跳过下线性求出单源最短路。在零一边权下用deque保持两个相邻距离层；Dial算法理路Dial 环形桶最短路算法Dial's algorithm · Dial bucket queue · Dial算法在零至C的整数边权图中，用C+1个循环复用的距离桶实现Dijkstra，明确绝对距离游标、旧记录与O(n+m+nC)总成本。将其推广到有限整数窗口，radix heap理路单调整数键的 Radix HeapRadix heap · 基数堆 · Binary radix heap在新键不小于最后弹出键的承诺下，按与该键的最高二进制差异位分桶，通过严格降桶的重分配跳过大片空键域。再按二进制差异跳过空键域。三者保留本页最小有效键结算的责任，不能因换队列而忽略旧项、键范围或字级成本。单对点查询还可采用双向Dijkstra理路双向 Dijkstra 与安全停止Bidirectional Dijkstra · 双向Dijkstra算法在正图与反图分别结算非负最短距离，持续维护已发现完整路径的上界，并以两队最小有效键之和认证停止。，在反图同时搜索，保存跨边可行上界并用两队首之和证明停止。

Johnson 算法理路Johnson 全源最短路算法Johnson's algorithm · Johnson all-pairs shortest paths以 Bellman–Ford 势函数把无负环图重赋为非负边权，再重复 Dijkstra 求稀疏图全源最短路。先用势函数把含负边、无负圈的图重赋为非负权，再逐源调用 Dijkstra。A*理路A* 搜索A* search · A-star search以已走代价与到目标的可采纳下界之和排序候选，并在一致性条件下保持最短路正确性的启发式搜索。在一致启发函数下等价于对约化非负权运行同一结算逻辑；对同一个固定目标和“目标结算即停止”的接口，令启发函数 $h\equiv 0$，A* 恰好退化为 Dijkstra 的单目标版本；特例关系采用这一共同接口。完整单源版本继续搜索其他可达顶点。