Ordered frontier and path · HTML
effort[v]=min over paths P of max step cost on P. Extending u to v gives cand=max(effort[u], step_cost(u,v)); retain the smaller label.
Recognition signals
- The objective says minimize the maximum, minimum required threshold, or bottleneck.
- A route is scored by its worst edge or vertex, not by a sum.
- Raising an allowed threshold can only add feasible paths, revealing monotone connectivity.
- The requested value is a minimum peak, water level, or capacity requirement needed to arrive.
False friends
| Signal | Why it is different |
|---|
| Maximize the minimum edge | That is a maximin or widest-path direction; comparisons and heap direction must change. |
| Minimum total cost | When every step accumulates, use additive Dijkstra instead. |
Core invariant
A fresh minimum-effort pop is final because extending any pending path cannot lower its bottleneck below its current frontier label.
State, transition, and processing order
| Item | Definition |
|---|
| State | best[v], the smallest bottleneck known to v, and heap labels (bottleneck,node). |
| Transition | Compute cand=max(current, edge_or_vertex_cost); if cand<best[v], update and push. |
| Frontier / order | A min-heap ordered by current bottleneck, expanding prefixes with the lowest achievable threshold first. |
Python skeleton
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')
Correctness sketch
- Max is monotone under extension: appending a step can never reduce a path's bottleneck.
- If a fresh minimum label u were not optimal, the first unsettled vertex on a better route would follow a settled predecessor that should have generated a lower candidate, contradiction.
- The relaxation exactly computes the bottleneck of a path extended through u, preserving every possible improvement.
Complexity
| Time | Space | Parameters |
|---|
| O(E log V) in the standard model; O(E log E) is valid for a lazy heap | O(V+E) worst case | V and E describe the state graph; every successful relaxation creates one heap label. |
Edge cases
- If the source vertex cost counts, initialize best[start] with that cost instead of zero.
- A one-vertex route depends on whether the source is scored.
- Zero-cost steps are valid.
- Use a documented sentinel for unreachable goals.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Using the wrong step metric | step_cost must match the bottleneck definition: edge difference, vertex height, and capacity are not interchangeable. |
| Pushing only when cand grows | Relaxation asks whether cand is smaller than best[v], not whether it exceeds the current path label. |
| Wrong source label | A vertex-weight model commonly includes the source's own cost. |
Selection and exclusion rules
- When path score is max and the outer objective is min, use minimax Dijkstra.
- Binary search plus connectivity is an alternative when can(T) is monotone and especially simple.
- For repeated undirected bottleneck queries, exploit MST path properties.
Original micro-example
| Part | Detail |
|---|
| Result | Choose the second route for minimax value 5. |
| Setup | Two routes have step costs [2,9,1] and [5,5,5]. |
| Trace | Their bottlenecks are 9 and 5; neither length nor sum is the score. |
Recall prompts
My notes