10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS

Between ordinary BFS and Dijkstra lies an interesting class of shortest-path problems.

Suppose edge weights are restricted to only two values:

0
1

Many practical problems naturally have this structure.

A routing system may assign cost 0 to preferred roads and cost 1 to secondary roads. A state-space search may assign cost 0 to free transitions and cost 1 to costly transitions. Grid problems often assign cost 0 to moving in a preferred direction and cost 1 to moving elsewhere.

Dijkstra solves these problems correctly, but it uses a priority queue. Since edge weights are limited to 0 and 1, we can exploit that structure to obtain a simpler and often faster algorithm.

This technique is called 0-1 BFS.

Problem

Given a graph whose edge weights are either:

compute the shortest path from a source vertex to every other vertex.

For example:

0 --0--> 1
|         |
1         0
|         |
v         v
2 --1--> 3

Starting from vertex 0, determine the minimum path cost to all vertices.

Solution

Instead of a priority queue, use a deque.

When relaxing:

A weight-0 edge inserts at the front.
A weight-1 edge inserts at the back.

package main

import (
	"container/list"
	"fmt"
)

type Edge struct {
	To     int
	Weight int
}

func zeroOneBFS(graph [][]Edge, source int) []int {
	const INF = int(1e18)

	dist := make([]int, len(graph))

	for i := range dist {
		dist[i] = INF
	}

	dist[source] = 0

	deque := list.New()
	deque.PushFront(source)

	for deque.Len() > 0 {
		element := deque.Front()
		deque.Remove(element)

		v := element.Value.(int)

		for _, edge := range graph[v] {
			candidate := dist[v] + edge.Weight

			if candidate >= dist[edge.To] {
				continue
			}

			dist[edge.To] = candidate

			if edge.Weight == 0 {
				deque.PushFront(edge.To)
			} else {
				deque.PushBack(edge.To)
			}
		}
	}

	return dist
}

func main() {
	graph := [][]Edge{
		{{1, 0}, {2, 1}},
		{{3, 0}},
		{{3, 1}},
		{},
	}

	fmt.Println(zeroOneBFS(graph, 0))
}

Output:

[0 0 1 0]

The shortest path to vertex 3 is:

0 -> 1 -> 3

with total cost:

0 + 0 = 0

Why a Deque Is Enough

Dijkstra uses a priority queue because arbitrary edge weights can produce arbitrary distance differences.

Suppose:

distance[v] = 10

and an edge has weight:

The resulting distance becomes:

A priority queue is necessary to maintain global ordering.

In a 0-1 graph, only two possibilities exist.

If:

distance[v] = d

then a neighboring vertex receives either:

or:

d + 1

Nothing else is possible.

Consequently, the deque always contains vertices whose distances differ by at most one.

This limited ordering is sufficient to preserve shortest-path correctness.

Visualizing the Queue

Suppose the deque currently contains:

[distance 3 vertices]

Processing a weight-0 edge produces:

distance 3

again.

That vertex belongs at the front.

Front
[3][3][3][4][4]
Back

Processing a weight-1 edge produces:

distance 4

which belongs at the back.

Front
[3][3][3][4][4][4]
Back

The deque naturally maintains distance order without requiring heap operations.

Understanding the Invariant

The key invariant resembles Dijkstra's algorithm.

At any moment:

Vertices near the front of the deque have the smallest known distances.

Weight-0 edges preserve distance.

Weight-1 edges increase distance by exactly one.

Because no larger jump is possible, inserting at the front or back is sufficient.

The deque effectively becomes a specialized priority queue with only two priority levels.

Relationship to BFS

Ordinary BFS assumes every edge has weight:

0-1 BFS extends this idea.

Algorithm	Allowed Weights
BFS	1
0-1 BFS	0, 1
Dijkstra	Any nonnegative weight

You can think of 0-1 BFS as the natural bridge between BFS and Dijkstra.

The data structures evolve similarly:

BFS      -> Queue
0-1 BFS  -> Deque
Dijkstra -> Priority Queue

Each step supports a larger class of edge weights.

Path Reconstruction

Path reconstruction works exactly as in Dijkstra.

Maintain a parent array.

parent := make([]int, n)

for i := range parent {
	parent[i] = -1
}

Whenever a better path is discovered:

dist[next] = candidate
parent[next] = current

The shortest path can later be reconstructed by following parent pointers backward.

No additional logic is required.

Grid Example

One of the most common uses of 0-1 BFS appears in grid problems.

Suppose each cell contains a preferred direction.

Moving in that direction costs:

Changing direction costs:

Example:

→ → ↓
↑ → ↓
↑ ↑ →

The objective is often:

Minimum number of direction changes

A graph can be constructed where:

Preferred moves have weight 0.
Nonpreferred moves have weight 1.

0-1 BFS then computes the optimal solution efficiently.

This pattern appears frequently in competitive programming and path-planning systems.

Discussion

The most important lesson from 0-1 BFS is not the algorithm itself.

It is the idea of exploiting problem structure.

General shortest-path algorithms solve broad classes of problems.

Specialized algorithms exploit additional constraints.

In this case:

Weights ∈ {0, 1}

is enough to eliminate the priority queue entirely.

This principle appears throughout algorithm design.

Every constraint is potentially an optimization opportunity.

Complexity

Each edge is relaxed at most a small number of times.

Deque operations are constant time.

Operation	Complexity
Push front	O(1)
Push back	O(1)
Pop front	O(1)
Total runtime	O(V + E)
Memory usage	O(V + E)

This matches ordinary BFS while supporting weighted edges.

Compared to Dijkstra:

Algorithm	Complexity
BFS	O(V + E)
0-1 BFS	O(V + E)
Dijkstra	O((V + E) log V)

For 0-1 graphs, the improvement can be substantial.

Common Mistakes

Do not use a standard queue. Weight-0 edges must be processed before weight-1 edges.

Do not use 0-1 BFS when weights larger than 1 exist.

Even a single edge of weight:

invalidates the algorithm.

Do not assume the deque contains globally sorted distances. The correctness argument is more subtle and depends on the limited weight range.

Do not forget that weight-0 edges belong at the front.

Reversing the insertion logic destroys correctness.

Practical Applications

0-1 BFS appears in:

Grid navigation problems
Network routing
State-space search
String transformation problems
Cost-minimization systems
Path-planning algorithms
Competitive programming contests
Transportation optimization

Many problems that appear to require Dijkstra become linear-time solutions once the weight structure is recognized.

Takeaway

0-1 BFS exploits a simple but powerful observation: when edge weights are restricted to 0 and 1, a deque can replace a priority queue. Weight-0 edges are processed immediately from the front, while weight-1 edges are deferred to the back. The result is a shortest-path algorithm with linear complexity that bridges the gap between ordinary BFS and Dijkstra's algorithm.