有序前沿与路径 · HTML
数学 / 逻辑形态
标签 effort[v]=min_P max(cost(x) for x in P)。从 u 扩展 v 时 cand=max(effort[u], step_cost(u,v))，取更小标签。
识别信号
- 目标措辞是 minimize the maximum、minimum required threshold 或 bottleneck。
- 路径只由其中最坏边/点决定，而非所有代价相加。
- 提高允许阈值只会增加可行路径，存在单调连通性。
- 需要到达目标时承受的最低峰值、最低水位或最小容量门槛。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 最大化最小边 | 这是 maximin/widest path；方向与比较符号需相应翻转。 |
| 总代价最小 | 如果每一步都累积贡献，仍是普通 Dijkstra 的加法标签。 |
核心不变量
非过期最小 effort 出堆时已最终：任何尚未展开路径的瓶颈不可能低于它当前经过的最小前沿标签。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | best[v] 表示到 v 的最小可能瓶颈，堆保存 (bottleneck,node)。 |
| Transition | cand=max(cur, edge_or_vertex_cost)；cand<best[v] 时更新并压堆。 |
| Frontier / order | 按当前瓶颈升序的最小堆；最低可实现阈值的路径前缀先扩展。 |
Python 骨架
import heapq
def minimax_path(graph, start, goal):
best = {start: 0}
heap = [(0, start)]
while heap:
effort, u = heapq.heappop(heap)
if effort != best.get(u):
continue
if u == goal:
return effort
for v, step_cost in graph.get(u, []):
cand = max(effort, step_cost)
if cand < best.get(v, float('inf')):
best[v] = cand
heapq.heappush(heap, (cand, v))
return float('inf')
正确性思路
- max 聚合具有单调扩展性：给路径追加一步不会降低其瓶颈。
- 若目标 u 的非过期最小标签并非最优，取更优路径上第一个未确定点；其前驱应已产生更小候选，矛盾。
- relaxation 精确比较经 u 到 v 的路径瓶颈，因此保留了所有可能改进。
复杂度
| Time | Space | Parameters |
|---|
| O(E log V) 标准表示；lazy heap 可写 O(E log E) | O(V+E) 最坏 | V、E 为状态图规模；每次成功 relaxation 产生一个堆项。 |
边界条件
- 起点自身代价若计入路径，best[start] 应初始化为该代价而非 0。
- 单节点路径答案取决于题目是否计起点。
- 零成本边合法。
- 目标不可达返回约定哨兵。
错误模式
| Pattern | Why it fails / fix |
|---|
| 误用绝对差或点高 | step_cost 必须与题目瓶颈定义一致：边差、点值或容量不可混用。 |
| 只在更大时 push | 松弛比较的是 cand 是否小于 best[v]，不是 cand 是否大于当前标签。 |
| 起点标签错 | 点权模型通常须把起点代价计入初始瓶颈。 |
选择与排除规则
- 路径评分为 max，目标对所有路径取 min：套 minimax Dijkstra。
- 若只要阈值且 can(T) 很便宜，也可二分答案 + 连通检查。
- 要多次查询无向瓶颈，可考虑 MST 的路径性质。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 选择第二条，minimax 值为 5。 |
| Setup | 两条路线的步代价分别为 [2,9,1] 与 [5,5,5]。 |
| Trace | 第一条瓶颈 9，第二条瓶颈 5；长度或总和不是评分标准。 |
Recall prompts
我的补充