0-1 BFS

Some graphs have only two kinds of edge: ones that cost nothing and ones that cost 1. A wall you walk past or a wall you break; a line you ride along or a line you must reverse. For these, a small change to breadth-first search gives the right answer at the same speed.

Costs of 0 and 1

Breadth-first search works because its queue always holds vertices of distance d, then vertices of distance d + 1, in that order (GRPH-2’s proof). Every edge adds exactly 1, so new vertices always belong at the back.

With an edge of cost 0, a vertex reached along it has the same distance as the vertex it came from. Putting it at the back breaks the order: vertices of distance d + 1 would be taken out before it. Step through “Plain BFS” in the figure: B is first reached by an edge of cost 1 and keeps that, although A → C → B costs 0 + 0.

The front and the back

The fix is a deque (STAQ-3, collections.deque), a queue that can add at both ends in O(1). A vertex reached by a cost-0 edge goes to the front, because it has the same distance as the vertex being handled. A vertex reached by a cost-1 edge goes to the back. And, as in Dijkstra’s method, a vertex is updated whenever a cheaper way to it is found, not only the first time it is reached.

from collections import deque
import math

def zero_one_bfs(adj, s):         # adj[u]: list of (v, w), w is 0 or 1
    dist = [math.inf] * len(adj)
    dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    q.appendleft(v)
                else:
                    q.append(v)
    return dist

A vertex can be in the deque twice: once from a cost-1 edge, and again, with a smaller value, from a cost-0 edge found later. When the older entry comes out, the vertex’s value is already smaller than the entry says; the figure hatches such entries and skips them. The code above does not need to skip them: handling the vertex again relaxes its edges with the same value as before, and nothing changes. Skipping saves the work, and the figure stores the value with each entry to show it.

Why the order is right

At the start it holds only s, with 0. Taking a vertex of value d from the front and adding a vertex of value d at the front, or d + 1 at the back, keeps the shape. So vertices come out in order of their value, as in Dijkstra’s method with a heap; the deque is a heap that only ever has two different values in it. When a vertex comes out with value d, no vertex with a smaller value is left, and edges cost at least 0, so nothing can lower it later: its value is final. Lesson 3 proves the same thing for Dijkstra in detail.

Cost. A vertex’s value can go down only once after it is first set: from d + 1 to d (values in the deque differ by at most 1). So each vertex enters the deque at most twice, each edge is relaxed at most twice, and the whole search is O(V + E), the same as breadth-first search, with no log V factor from a heap.

Where 0 and 1 appear

• Walls to break. GRPH-7 counted moves with at most k walls broken, by searching states (square, walls used). If the question is only “fewest walls broken”, a step into a free square costs 0 and a step into a wall costs 1, and 0-1 BFS on the squares answers it with no extra state.
• Lines to reverse. Riding along a one-way line costs 0; riding against it, by reversing it, costs 1. That is PATH-P2.
• Changes of direction. In a grid of arrows, following a square’s arrow costs 0 and changing it costs 1. In a maze where turning costs 1, the state is (square, direction), and going straight on costs 0.
• Changes of line. On a metro map, staying on the same line costs 0 and changing lines costs 1: the state is (station, line).

Now try PATH-P2, Fewest lines to reverse.