Ordered frontier and path · HTML
Set dist[s]=0. FIFO expands vertices in nondecreasing distance; the first discovery of v assigns dist[v]=dist[u]+1.
Recognition signals
- Every action counts exactly once and has identical cost.
- The objective says minimum moves, fewest transformations, or nearest target.
- The state graph can be generated lazily rather than stored.
- A nearest-source problem can seed every source in layer zero.
False friends
| Signal | Why it is different |
|---|
| Weights of both 0 and 1 | Small is not equal; FIFO layers cease to equal cost, so use 0-1 BFS. |
| Reachability only | If distance is unused, component BFS or DFS is enough; avoid unnecessary layer machinery. |
Core invariant
Dequeued distances are nondecreasing, and a vertex's discovery distance is the minimum edge count from any source.
State, transition, and processing order
| Item | Definition |
|---|
| State | FIFO queue, dist map that can also serve as visited, current state, and optional parent map. |
| Transition | Generate each eligible unseen neighbor v of u, set dist[v]=dist[u]+1, and enqueue it. |
| Frontier / order | A FIFO queue whose head belongs to the smallest pending layer because every edge adds exactly one. |
Python skeleton
from collections import deque
def shortest_steps(start, is_goal, neighbors):
q = deque([start])
dist = {start: 0}
while q:
u = q.popleft()
if is_goal(u):
return dist[u]
for v in neighbors(u):
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return -1
Correctness sketch
- FIFO completes layer d before d+1, so dequeue distances never decrease.
- If a first-discovery path were not shortest, a predecessor on a shorter path would have appeared in an earlier layer and discovered the same vertex first.
- When a goal is dequeued, every potentially shorter state has already been expanded, making early exit safe.
Complexity
| Time | Space | Parameters |
|---|
| O(V+E) | O(V) | V and E count reachable states and generated transitions, including in an implicit graph. |
Edge cases
- Return 0 when the source is already a goal.
- Return a documented sentinel when the queue exhausts.
- Multi-source BFS must assign distance 0 to every source.
- Large compound states may require a compact hashable encoding.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Returning on generated goal | It is correct for standard equal-cost BFS, but checking after pop gives a safer reusable frontier convention. |
| Off-by-one layer counters | A distance stored per vertex is often more robust than manual round increments. |
| Mixing validity with visited | Validate a generated state before testing whether it was discovered. |
Selection and exclusion rules
- Use BFS when every transition has one identical positive cost.
- Use 0-1 BFS when transition costs are only zero or one.
- For distance to the nearest of equivalent sources, enqueue all sources together.
Original micro-example
| Part | Detail |
|---|
| Result | The minimum is 3 moves, for example 0→2→4→5. |
| Setup | A state x can become x-1 or x+2 per move; go from 0 to 5. |
| Trace | Layer 0={0}; layer 1={-1,2}; layer 2 includes 1 and 4; layer 3 first reaches 5. |
Recall prompts
My notes