Module 21 · Union-Find, Weighted Graphs, and Minimum Spanning Trees

210. Zero-One BFS

Interview · Download this solution · All solutions and shared helpers

Problem

Compute shortest distances from a valid source in a directed adjacency list whose weights are only zero or one. Return None for unreachable vertices. Parallel edges and cycles are allowed. Use a deque instead of a general priority heap.

Examples

Example 1

zero_one_bfs([[(1,1),(2,0)],[],[(1,0)],[]],0)
=> [0, 0, 0, None]

The zero-cost detour improves the initially proposed cost of vertex 1.

Example 2

zero_one_bfs([[(0,0),(1,1)],[]],0)
=> [0, 1]

A zero self-loop cannot cause a strict improvement.

Example 3

zero_one_bfs([[]],0)
=> [0]

The source distance is zero.

Reveal the worked solution and reasoning

Why this mechanism works

From a minimum-distance vertex, a zero edge stays in the current distance bucket and belongs at the deque's front; a one edge belongs at the back. This maintains the required distance order with only two adjacent distance levels. Keep distance-tagged entries so an old proposal can be skipped after a later improvement.

State and boundaries

dist records best discovered costs. Nonstale deque entries are processed in nondecreasing distance; zero-cost improvements go before one-cost work.

Protocol

Initialize source at zero.
Pop from the deque front.
Skip stale entries.
Relax each outgoing edge.
Push an improved zero-edge route to the front, or a one-edge route to the back.
Convert unreachable infinities to None.

Visualization

0->1 weight 1; 0->2 weight 0; 2->1 weight 0
deque front favors 2 at distance 0
then improves 1 from 1 to 0 before stale work is used

Python implementation

from collections import deque

def zero_one_bfs(adj, source):
    dist = [float('inf')] * len(adj)
    dist[source] = 0
    queue = deque([(0, source)])
    while queue:
        distance, u = queue.popleft()
        if distance != dist[u]:
            continue
        for v, weight in adj[u]:
            candidate = distance + weight
            if candidate < dist[v]:
                dist[v] = candidate
                entry = (candidate, v)
                if weight == 0:
                    queue.appendleft(entry)
                else:
                    queue.append(entry)
    return [None if value == float('inf') else value for value in dist]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

zero_one_bfs([[(1,1),(2,0)],[],[(1,0)],[]],0)

L4 zero_one_bfs: dist = [float('inf')] * len(adj)
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[inf, inf, inf, inf]

L5 zero_one_bfs: dist[source] = 0
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]

L6 zero_one_bfs: queue = deque([(0, source)])
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; queue=deque([(0, 0)])

L8 zero_one_bfs: distance, u = queue.popleft()
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; queue=deque([]); distance=0; u=0

L11 zero_one_bfs: for v, weight in adj[u]:
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; queue=deque([]); distance=0; u=0; v=1; weight=1

L12 zero_one_bfs: candidate = distance + weight
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; queue=deque([]); distance=0; u=0; v=1; weight=1; candidate=1

L14 zero_one_bfs: dist[v] = candidate
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 1, inf, inf]; queue=deque([]); distance=0; u=0; v=1; weight=1; candidate=1

L15 zero_one_bfs: entry = (candidate, v)
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 1, inf, inf]; queue=deque([]); distance=0; u=0; v=1; weight=1; candidate=1; entry=(1, 1)

... 12 intermediate state changes omitted ...

L8 zero_one_bfs: distance, u = queue.popleft()
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 0, 0, inf]; queue=deque([]); distance=1; u=1; v=1; weight=0; candidate=0; entry=(0, 1)

L20 zero_one_bfs: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 0, 0, inf]; queue=deque([]); distance=1; u=1; v=1; weight=0; candidate=0; entry=(0, 1); value=0

L20 zero_one_bfs: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 0, 0, inf]; queue=deque([]); distance=1; u=1; v=1; weight=0; candidate=0; entry=(0, 1); value=inf

L20 zero_one_bfs: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 0, 0, inf]; queue=deque([]); distance=1; u=1; v=1; weight=0; candidate=0; entry=(0, 1)

Result: [0, 0, 0, None]. The zero-cost detour improves the initially proposed cost of vertex 1.

zero_one_bfs([[(0,0),(1,1)],[]],0)

L4 zero_one_bfs: dist = [float('inf')] * len(adj)
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[inf, inf]

L5 zero_one_bfs: dist[source] = 0
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]

L6 zero_one_bfs: queue = deque([(0, source)])
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]; queue=deque([(0, 0)])

L8 zero_one_bfs: distance, u = queue.popleft()
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]; queue=deque([]); distance=0; u=0

L11 zero_one_bfs: for v, weight in adj[u]:
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]; queue=deque([]); distance=0; u=0; v=0; weight=0

L12 zero_one_bfs: candidate = distance + weight
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]; queue=deque([]); distance=0; u=0; v=0; weight=0; candidate=0

L11 zero_one_bfs: for v, weight in adj[u]:
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]; queue=deque([]); distance=0; u=0; v=1; weight=1; candidate=0

L12 zero_one_bfs: candidate = distance + weight
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, inf]; queue=deque([]); distance=0; u=0; v=1; weight=1; candidate=1

... 3 intermediate state changes omitted ...

L8 zero_one_bfs: distance, u = queue.popleft()
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, 1]; queue=deque([]); distance=1; u=1; v=1; weight=1; candidate=1; entry=(1, 1)

L20 zero_one_bfs: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, 1]; queue=deque([]); distance=1; u=1; v=1; weight=1; candidate=1; entry=(1, 1); value=0

L20 zero_one_bfs: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, 1]; queue=deque([]); distance=1; u=1; v=1; weight=1; candidate=1; entry=(1, 1); value=1

L20 zero_one_bfs: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], []]; source=0; dist=[0, 1]; queue=deque([]); distance=1; u=1; v=1; weight=1; candidate=1; entry=(1, 1)

Result: [0, 1]. A zero self-loop cannot cause a strict improvement.

Why the solution is correct

The front/back rule preserves the ordering that Dijkstra needs because every new distance is current or current+1. Therefore a nonstale minimum removal has its optimal distance. Each vertex's outgoing edges are processed when finalized, and strict improvements prevent endless zero-cycle scheduling.

Time and space

O(V+E) time and O(V+E) auxiliary space with lazy distance-tagged proposals; each edge can create at most one proposal when its source is processed.

Common mistakes

Appending zero-cost edges at the back loses the distance-order proof. A visited-on-enqueue rule rejects later zero-cost improvements. Weights outside {0,1} require a different frontier.

Reasoning card

State: dist records best discovered costs. Nonstale deque entries are processed in nondecreasing distance; zero-cost improvements go before one-cost work.

Invariant: Deque ordering preserves nondecreasing tentative distance.

Decision to rehearse: Push weight-0 transitions to deque front and weight-1 to back.

Finish: Convert unreachable infinities to None

Transfer exercise

Generalize to small integer weights with cyclic distance buckets, stating how many buckets are required.