# BFS for Shortest Paths — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/g-bfs

> Unweighted graphs and grids.

## 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.

![Four ideas: BFS shortest paths, components, topological sort, weighted shortest paths.](assets/figures/dsa-interview-patterns/section-6-map.svg) — Figure 6.1 — BFS, components, topological sort and Dijkstra.

## 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.

```python
# 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.

**Quiz:** Why does BFS find shortest paths in unweighted graphs?

- [ ] It uses a priority queue
- [ ] It explores randomly
- [x] It explores nodes in increasing order of distance
- [ ] It visits deepest nodes first

*Answer:* It explores nodes in increasing order of distance. Layer by layer.