土法炼钢 · 系统与基础设施

Dijkstra 与 A*：非负权、启发式与工程优先队列

2026-06-03 | algorithms | #dijkstra #a-star #shortest-path #priority-queue #pathfinding #contraction-hierarchies

从 Dijkstra 的 label-setting 不变式出发，解释负权反例、A* 的可采纳与一致启发式、reduced cost 等价关系，并用可复现 C 程序按扩展节点、出堆、松弛与 decrease-key 次数比较实现取舍。