Shortest Path in a Binary Matrix

Shortest Path in a Binary Matrix is the cleanest possible introduction to breadth-first search on a grid. The grid is full of open cells and walls, and we want the fewest steps from one corner to the other — exactly the kind of "shortest path on an unweighted graph" that BFS was made for.

The slow way first

You could try DFS — wander down one route, backtrack, try another, and keep the best length you find. But DFS explores deep before wide, so it happily walks a long route first and may revisit the same cell many times along different paths. To be sure a path is shortest you would have to explore essentially all of them. That blows up fast.

The question to ask: can I explore cells in order of distance, so the first time I touch the goal I already know it is the closest? That is exactly what BFS does.

The idea: spread outward one ring at a time

BFS uses a queue. Start at (0,0) with distance 1. Repeatedly pop a cell, and push all of its open, unvisited 8-neighbors with distance + 1. Because the queue processes cells in the order they were added, every cell at distance d is handled before any cell at distance d + 1 — the search expands like a growing ring.

The key insight: the first time the goal comes out of the queue, its recorded distance is the shortest path length. No other route could have been shorter, because we visit cells strictly in increasing distance order. Mark a cell the moment you push it so it is never queued twice.

Walk through it

Step through the animation. The wavefront starts at the top-left and grows outward: each ring of cells lights up as comparing when it enters the queue, then dims to visited when it is popped and expanded. Walls (1) are never entered. When the ring finally reaches the bottom-right corner, the distance label reads 5, and the highlighted cells trace one shortest path back to the start.

Pseudocode

if start or goal is a wall: return -1
queue = [(0, 0, distance = 1)]
mark (0,0) as visited
while queue is not empty:
    (r, c, d) = pop front of queue
    if (r, c) is the goal: return d
    for each of the 8 neighbors (nr, nc):
        if (nr, nc) is in bounds, open, and unvisited:
            mark it visited
            push (nr, nc, d + 1)
return -1            # queue emptied without reaching the goal

The Python solution

def shortest_path(grid):
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1
    q = deque([(0, 0, 1)])
    grid[0][0] = 1
    while q:
        r, c, d = q.popleft()
        if r == n-1 and c == n-1:
            return d
        for dr, dc in DIRS:  # 8 neighbors
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 1
                q.append((nr, nc, d + 1))
    return -1

• We bail out early if either corner is a wall — there is no path then.
• The queue holds (row, col, distance) triples; the start gets distance 1.
• grid[0][0] = 1 marks the start visited by overwriting it — a tidy way to avoid a separate visited set.
• Popping with q.popleft() is what makes this BFS: cells leave the queue in the order of increasing distance.
• The goal check happens when a cell is popped, so its d is final and shortest.
• DIRS is the 8 offset pairs; we mark each neighbor visited before queueing it so it is enqueued only once.

Complexity

Every cell is pushed and popped at most once, and each pop checks a constant 8 neighbors, so the whole search is O(n²) for an n x n grid. The queue and visited marking use O(n²) space in the worst case.

When this pattern shows up

Practice