The idea: BFS with a deque

Breadth-first search finds shortest paths when every edge costs 1: a plain queue hands out vertices in order of distance. Dijkstra's algorithm handles any weights that are not negative, but it needs a heap. When every weight is 0 or 1 there is a middle way, 0-1 BFS: keep a deque (a double-ended queue). A vertex reached over a 0-edge is exactly as far as the vertex it came from, so it goes to the front. A vertex reached over a 1-edge is one step further, so it goes to the back.

A deque of entries B·0, A·0 at the front and A·1, C·1 at the back. The front half holds distance d, the back half d plus 1. An arrow from a 0-edge goes into the front, an arrow from a 1-edge goes into the back; pop always takes the front.
The deque only ever holds two distances, d at the front and d + 1 at the back, so the front is always the closest vertex.

The algorithm

dist[s] = 0, dist[v] = ∞ for every other v
deque = [(s, 0)]
while deque not empty:
    (u, d) = pop_front(deque)
    if d > dist[u]: continue              # stale copy, skip
    for each edge u→v with weight w (0 or 1):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u
            if w == 0: push_front(deque, (v, dist[v]))
            else:      push_back(deque, (v, dist[v]))

On the sample graph the answer is dist[T] = 1 along S → B → A → D → T, which uses four edges but only one of weight 1 (Demo: 0-1 BFS with a deque). S first pushes A·1 to the back and B·0 to the front. B is popped next and finds A for 0, so A·0 goes to the front.

Stale entries

A vertex can be in the deque twice. Above, A·1 is still in the deque when A·0 is pushed in front of it. The deque never searches for an old copy to remove it. Instead each entry carries the distance it was pushed with, and when an entry is popped with d > dist[v] it is stale and skipped. A vertex is improved at most twice in total (once to some d + 1, once to d), so the deque never holds more than 2V entries.

Why the front is always the closest

The deque keeps an invariant: read from front to back, its distances are sorted and there are at most two of them, d and d + 1. Popping the front takes a vertex at d. Its 0-edges add vertices at d, which belong at the front. Its 1-edges add vertices at d + 1, which belong at the back. Both pushes keep the order. So vertices come out in order of distance, exactly the order Dijkstra would settle them in, and a vertex popped (not stale) has its final distance. The deque is doing the heap's job for free.

Two ways to get it wrong

Plain BFS ignores the weights. It fixes a vertex the first time it sees it, which is along the path with the fewest edges. From S it sees A over the 1-edge first, then D through A, then T: dist[T] = 2 along S → A → D → T, three edges (Demo: plain BFS counts edges). The edge B→A = 0 comes too late.

A queue that pushes 0-edges to the back too breaks the invariant. S pushes A·1 and then B·0, both at the back, so the queue reads A·1, B·0: not sorted. A is popped and treated as final at 1 before B gets the chance to offer 0 (Demo: 0-edges to the back too). The answer is again 2.

MethodData structureWeightsTimeSample graph
Plain BFSqueueall 1O(V + E)T = 2 ✗
Queue, 0 at the backqueue—O(V + E)T = 2 ✗
0-1 BFSdeque0 or 1O(V + E)T = 1 ✓
Dijkstrabinary heapany w ≥ 0O((V + E) log V)T = 1 ✓

With every weight 1 nothing is ever pushed to the front, and 0-1 BFS does exactly what plain BFS does: both find dist[T] = 3 (Demo: all weights 1). 0-1 BFS is BFS with one extra rule for 0-edges.

Where 0/1 weights come from

Many problems have moves that are free and moves that cost one unit. In a grid, walking into an open cell is free and walking into a wall cell means breaking it: 0-1 BFS gives the fewest walls to break. Other examples: free roads and toll roads, keeping a direction (0) or turning (1), and following an edge the right way (0) or reversing it (1) to make a path exist. See grid pathfinding for BFS and A* on grids.

A 4 by 6 grid with grey wall cells. Each cell shows its 0-1 BFS distance from the start in the top left: open cells keep the number, walls add one. The green route to the bottom right corner breaks only one wall, cost 1.
Fewest walls to break: stepping into an open cell costs 0, into a wall 1.

Cost

Every vertex is finished once and every edge relaxed at most once from a finished vertex, and each deque operation is O(1), so 0-1 BFS runs in O(V + E), against O((V + E) log V) for Dijkstra with a binary heap. The same trick grows to small integer weights 0 … k: Dial's algorithm keeps k + 1 buckets instead of two ends. For negative weights neither works: use Bellman-Ford, or the one-pass method for shortest paths in a DAG.

The deque here is usually a circular buffer; Deque shows how push_front and push_back stay O(1).

What the page leaves out

Dial's bucket queue step by step; undirected graphs (each edge is two directed edges); the grid problem on the canvas (only in the figure above); a version that marks vertices visited instead of checking stale distances; and how a deque is stored (a ring buffer or blocks of arrays).