有序前沿与路径 · HTML
数学 / 逻辑形态
dist[s]=0；对边 u→v,w≥0 做 relaxation：cand=dist[u]+w。堆弹出的非过期最小标签即为最终最短距离。
识别信号
- 目标是路径上代价、延迟或长度的总和最小。
- 每条转移成本已知且非负。
- 普通 BFS 因边权不等而失去分层保证。
- 需要单源到一处或多处的最短距离。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 存在负权边 | 已弹出标签仍可能被负边改善，Dijkstra 的贪心证明失效。 |
| 路径最大值最小 | 聚合器不是加法；应改用 minimax-dijkstra 的 max relaxation。 |
核心不变量
每次弹出的非过期标签 (d,u) 是所有未确定路径标签中的最小值；非负边保证任何绕行都不能把 u 降到 d 以下。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | dist[v] 暂定最短和、最小堆中的 (distance,node)，以及可选 parent。 |
| Transition | 对 u→v,w 计算 nd=d+w；若 nd<dist[v]，更新 dist 并把新标签压堆。 |
| Frontier / order | 按暂定距离排序的 min-heap；Python 用重复入堆 + lazy deletion 代替 decrease-key。 |
Python 骨架
import heapq
def dijkstra(graph, start, goal=None):
dist = {start: 0}
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d != dist.get(u):
continue
if goal is not None and u == goal:
return d
for v, w in graph.get(u, []):
if w < 0:
raise ValueError('negative edge')
nd = d + w
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist if goal is None else float('inf')
正确性思路
- 设 u 是首次弹出的非过期最小标签；若存在更短路径，取该路径上第一个未确定点，其前驱已确定并应产生更小候选，矛盾。
- relaxation 枚举每条可能成为更优前缀的边，因此不会错过最短路径。
- 过期堆项不等于当前 dist 时跳过，不改变任何仍可能最优的标签。
复杂度
| Time | Space | Parameters |
|---|
| O((V+E) log H)，通常写 O(E log V) | O(V+H)，lazy heap 最坏 H=O(E) | V 为点、E 为边，H 为堆中同时存在的标签数；理论 decrease-key 堆可令 H≤V，Python 重复入堆常写 O(E log E)，且简单图中 log E=O(log V)。 |
边界条件
- 起点等于目标时首次弹出即返回 0。
- 不可达目标返回 inf 或约定哨兵。
- 零权边完全合法。
- 平行边会由 relaxation 自动保留更优者。
错误模式
| Pattern | Why it fails / fix |
|---|
| 把起点放进 visited 后又跳过 | 初始化 visited={start} 且 pop 时检查会直接丢失起点。 |
| push 时就最终确定 | 节点可能后来被更短路径改善；最终性只在非过期 pop 时成立。 |
| 忘记更新 dist | 压堆与 dist 赋值必须属于同一次成功 relaxation。 |
选择与排除规则
- 等权边优先 BFS，0/1 权优先 0-1 BFS，一般非负权用 Dijkstra。
- 只求单一目标时在目标非过期出堆后早退。
- Python 默认使用 dist + lazy deletion，不必模拟 decrease-key。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | s 到 a 的最短和为 3。 |
| Setup | s→a 成本 7，s→b 成本 2，b→a 成本 1。 |
| Trace | 先压 a:7、b:2；弹 b 后把 a 改善为 3；a:3 先于过期 a:7 弹出。 |
Recall prompts
我的补充