BFS for Shortest Paths

Distance by layers

In an unweighted graph, BFS visits nodes in order of distance, so the first time it reaches the goal is via a shortest path. Grids are implicit graphs: neighbours are the four (or eight) adjacent cells that are in bounds and not walls. Mark nodes as visited when enqueued, not when dequeued, to avoid adding the same node many times. Multi-source BFS starts with several nodes in the queue (for example rotting oranges).

Nodes, edges and order

Grids, dependencies and networks are graphs; BFS, DFS, union-find, topological sort and Dijkstra cover most questions.

Shortest path in a grid with walls, run

I ran this with Python 3.12.3 (standard library only). Two reachable goals return their path lengths (10 and 4); a goal blocked by walls returns -1.

# Grid BFS: shortest path length avoiding walls (#)
from collections import deque

def shortest_path(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    q, seen = deque([(start, 0)]), {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == goal:
            return d
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append(((nr, nc), d + 1))
    return -1

grid = ["..#....",
        ".##.##.",
        "....#..",
        "#.#...#"]
print(shortest_path(grid, (0, 0), (0, 6)))
print(shortest_path(grid, (0, 0), (3, 1)))
print(shortest_path([".#", "#."], (0, 0), (1, 1)))

Output:

10
4
-1

Use a direction list

A tuple of (dr, dc) pairs keeps neighbour code short and less error-prone.

Quick check: Why does BFS find shortest paths in unweighted graphs?

• It uses a priority queue
• It explores randomly
• It explores nodes in increasing order of distance
• It visits deepest nodes first