Dijkstra 与 A*：非负权、启发式与工程优先队列
内容提要
本文澄清最短路算法的三大常见误解：Dijkstra算法要求非负权，负权反例表明无负环也不够；Fibonacci堆理论复杂度优，但工程实践中常不如简洁堆；A*启发式须可采纳，一致时才可关闭节点。实验对比了惰性删除与decrease-key，并介绍双向搜索、ALT、CH及OSRM实现。
延伸解读
负权边：Dijkstra 的绝对禁区
文章通过一个无负环的反例表明，即使图中没有负环，只要存在负权边，Dijkstra 也可能出错。这是因为 Dijkstra 是 label-setting 算法，顶点一旦出堆就被永久确定，而负权边可能使已确定的距离不再是最短。因此，工程中若检测到负权边，应改用 Bellman-Ford 或 Johnson 重加权，而不是强行使用 Dijkstra。
优先队列选择：理论 vs 工程
Fibonacci 堆在理论上能实现 O(m + n log n) 的 Dijkstra，但其复杂结构和差缓存局部性常导致实际性能不如简洁的二叉堆。文章实验显示，lazy deletion 虽无 decrease-key，但出堆次数约是 indexed heap 的两倍，多出的都是 stale entry。选择哪种实现需权衡语言库、内存和缓存行为，而非只看渐近复杂度。
A* 启发式：可采纳与一致性的关键区别
A* 要求启发式可采纳（不高估真实剩余距离）才能保证最优。若启发式还满足一致性（三角不等式），则 A* 像 Dijkstra 一样，节点首次出堆即可关闭，无需重新打开。工程中若使用不一致启发式，必须支持 reopen，否则可能得到次优解。weighted A* 通过放大启发式牺牲最优性，应明确视为近似策略。
道路图加速：从双向搜索到 CH 与 ALT
对于大规模道路网络，单次 Dijkstra 往往不够。双向搜索需用正确停止条件（p_f + p_b ≥ μ），而非首次相遇即停。ALT 利用地标和三角不等式得到更紧下界，适合部分动态权重；CH 通过预处理收缩节点和 shortcut 实现低延迟查询，但边权频繁变化时需重新预处理。OSRM 的源码显示其使用 4 叉可变堆，而非 Fibonacci 堆，体现了工程取舍。
Q&A
Dijkstra 算法为什么要求边权非负？
Dijkstra 是 label-setting 算法，顶点一旦出堆就被永久确定。非负边权保证：当弹出当前最小临时距离的顶点 u 时，后续任何路径都不可能再把 d[u] 降低。若存在负权边，即使没有负环，也可能先确定了一个顶点，之后又发现更短路径，导致结果错误。
Fibonacci 堆在工程中是否比二叉堆更适合实现 Dijkstra？
不一定。Fibonacci 堆理论复杂度更优（O(m + n log n)），但实现复杂、缓存局部性差。实际机器上，简洁的二叉堆往往因更好的缓存行为而表现更佳。工程选择应权衡语言库、内存、查询模式等因素，而非仅看渐近复杂度。
A* 算法中启发式函数需要满足什么条件才能保证找到最短路径？
启发式必须可采纳（admissible），即对所有顶点 v，h(v) ≤ δ(v,t)，不高估真实剩余距离。若启发式一致（consistent），即满足三角不等式 h(u) ≤ w(u,v) + h(v) 且 h(t)=0，则 A* 可像 Dijkstra 一样在节点第一次出堆时关闭，无需重新打开。
在实现 Dijkstra 时，lazy deletion 和 decrease-key 两种堆操作方式各有什么优缺点？
lazy deletion 在距离变小时直接插入新键，出堆时丢弃过期条目，实现简单但会增加出堆次数（约两倍）。decrease-key 维护索引，每个顶点只出现一次，出堆次数等于顶点数，但需要额外维护位置信息。选择取决于语言库、内存和缓存局部性。
双向 Dijkstra 搜索的正确停止条件是什么？
不能一相遇就停止。正确条件是维护当前最短路径上界 μ，当正向队列最小键 p_f 与反向队列最小键 p_b 满足 p_f + p_b ≥ μ 时才能停止。第一次相遇只给出上界，不是证明。
OSRM 在道路网络最短路径查询中使用了哪些加速技术？
OSRM 使用了 Contraction Hierarchies (CH) 和 Multi-Level Dijkstra (MLD)。CH 通过预处理添加 shortcut 并做上坡双向搜索；MLD 使用多层 Dijkstra 堆。查询堆基于 boost::heap::d_ary_heap（4 叉堆），支持 decrease-key，而非 Fibonacci 堆。
