Ordered frontier and path · HTML
Relax u→v,w∈{0,1}; after improvement, appendleft for w=0 and append for w=1, keeping pending labels within adjacent cost buckets.
Recognition signals
- Actions split into free and one-charge transitions.
- Every edge weight is exactly in {0,1}.
- The objective minimizes paid actions, not total moves.
- Dijkstra would work but its binary heap is unnecessary overhead.
False friends
| Signal | Why it is different |
|---|
| All actions equal | If every edge costs one, ordinary BFS is simpler. |
| Weights zero and arbitrary positive values | Two deque ends encode only two adjacent priorities; general nonnegative weights need Dijkstra. |
Core invariant
Pending candidate distances are nondecreasing from left to right; a zero edge stays in the current cost layer and a one edge enters the next.
State, transition, and processing order
| Item | Definition |
|---|
| State | Distance map, deque of vertices or labels, and a generator of binary-weight edges. |
| Transition | If nd=dist[u]+w improves v, assign it; put v on the left for w=0 and right for w=1. |
| Frontier / order | A deque acting as a bucket priority queue with exactly two relative priorities. |
Python skeleton
from collections import deque
def zero_one_bfs(graph, start):
inf = float('inf')
dist = {u: inf for u in graph}
dist[start] = 0
dq = deque([start])
while dq:
u = dq.popleft()
for v, w in graph[u]:
if w not in (0, 1):
raise ValueError('weight must be 0 or 1')
nd = dist[u] + w
if nd < dist.get(v, inf):
dist[v] = nd
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
Correctness sketch
- The leftmost pending label has minimum cost: zero edges remain in its layer and one edges enter only the next layer.
- Every relaxation creates an actual path upper bound and places an improved label at its proper relative priority.
- This is Dijkstra on binary weights compressed into two buckets, so the finalized distances are optimal.
Complexity
| Time | Space | Parameters |
|---|
| O(V+E) | O(V) | Each successful improvement uses O(1) deque operations; standard binary-weight relaxation scans stay linear in graph size. |
Edge cases
- With all zero edges, every reachable vertex has distance zero.
- With all one edges, the method degenerates to BFS.
- A zero-weight cycle must not be frozen by premature first-seen visited logic.
- Reject an out-of-domain weight or switch algorithms.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Appending zero edges on the right | A free candidate falls behind costlier candidates and breaks frontier order. |
| Visited without distances | A vertex first seen at cost one can later improve through a free prefix. |
| Counting edges instead of cost | The result counts one-weight edges, not total transitions. |
Selection and exclusion rules
- Prefer 0-1 BFS when the weight set is exactly {0,1}.
- Weights {0,c} for one fixed positive c can be scaled to the same template.
- Return to Dijkstra as soon as a third distinct priority appears.
Original micro-example
| Part | Detail |
|---|
| Result | The minimum cost to a is 0, not its first-discovered value 1. |
| Setup | s→a costs 1, s→b costs 0, and b→a costs 0. |
| Trace | a:1 first sits right; b:0 goes left. Popping b improves a to 0 and puts it left. |
Recall prompts
My notes