Shortest Path in Grid: BFS, 0-1 BFS, and Dijkstra on Grids

Grids are graphs in disguise. Every cell is a vertex, and edges connect each cell to its 4 (or 8) neighbors. Once you see grids as graphs, shortest path algorithms apply directly. The question is: which algorithm fits your grid?

The answer depends on edge weights. Unweighted grids (all moves cost 1) use BFS. Binary-weight grids (moves cost 0 or 1) use 0-1 BFS. Grids with varied non-negative weights use Dijkstra.

Standard BFS on Unweighted Grid

When every move costs 1, BFS finds the shortest path. This is the most common grid pattern.

from collections import deque

def shortest_path_bfs(grid: list[list[int]], 
                       start: tuple[int, int], 
                       end: tuple[int, int]) -> int:
    """
    Find shortest path in grid where 0 = passable, 1 = wall.
    Returns number of steps, or -1 if no path exists.
    """
    rows, cols = len(grid), len(grid[0])
    if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1:
        return -1
    
    queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
    visited = {(start[0], start[1])}
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        r, c, dist = queue.popleft()
        
        if (r, c) == end:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and 
                grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    
    return -1

Why BFS Works for Unweighted Graphs

BFS processes nodes in order of their distance from the source. Level 0 (distance 0) is processed first, then level 1, then level 2, and so on. The first time you reach any node, you have found the shortest path to it. This is guaranteed because all edges have the same weight.

Shortest Path in Binary Matrix (LeetCode 1091)

Find the shortest path from top-left to bottom-right in a binary matrix, moving in 8 directions.

def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    """
    LeetCode 1091: Shortest path in binary matrix (8-directional).
    0 = passable, 1 = blocked.
    """
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    # 8 directions including diagonals
    dirs = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
    
    queue = deque([(0, 0, 1)])  # (row, col, path_length)
    visited = {(0, 0)}
    
    while queue:
        r, c, length = queue.popleft()
        
        if r == n - 1 and c == n - 1:
            return length
        
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if (0 <= nr < n and 0 <= nc < n and 
                grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, length + 1))
    
    return -1

Multi-Source BFS

Sometimes the “source” is not a single cell but many cells simultaneously. Multi-source BFS adds all source cells to the queue at once, then expands outward.

Rotting Oranges (LeetCode 994)

Every minute, fresh oranges adjacent to rotten ones become rotten. Find the minimum time until all oranges are rotten.

def orangesRotting(grid: list[list[int]]) -> int:
    """
    LeetCode 994: Multi-source BFS from all rotten oranges.
    0 = empty, 1 = fresh, 2 = rotten.
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # Add all rotten oranges as sources
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh_count += 1
    
    if fresh_count == 0:
        return 0
    
    max_time = 0
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    
    while queue:
        r, c, time = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and 
                grid[nr][nc] == 1):
                grid[nr][nc] = 2
                fresh_count -= 1
                max_time = time + 1
                queue.append((nr, nc, time + 1))
    
    return max_time if fresh_count == 0 else -1

Walls and Gates (LeetCode 286)

Fill each empty room with the distance to its nearest gate. Classic multi-source BFS.

def wallsAndGates(rooms: list[list[int]]) -> None:
    """
    LeetCode 286: Multi-source BFS from all gates.
    -1 = wall, 0 = gate, INF = empty room.
    """
    if not rooms:
        return
    
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    queue = deque()
    
    # All gates are sources
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
    
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and 
                rooms[nr][nc] == INF):
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

0-1 BFS with Deque

When edge weights are either 0 or 1, you can use a deque instead of a priority queue. Add weight-0 edges to the front and weight-1 edges to the back. This maintains the BFS invariant that the queue is sorted by distance.

from collections import deque

def shortest_path_01_bfs(grid: list[list[int]], 
                          start: tuple, end: tuple) -> int:
    """
    0-1 BFS on a grid where some moves cost 0 and others cost 1.
    grid values: 0 = free (cost 0), 1 = wall (cost 1 to break).
    """
    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[start[0]][start[1]] = 0
    
    dq = deque([(0, start[0], start[1])])  # (cost, row, col)
    
    while dq:
        cost, r, c = dq.popleft()
        
        if cost > dist[r][c]:
            continue
        
        if (r, c) == end:
            return cost
        
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                # Cost to move depends on whether destination is a wall
                move_cost = grid[nr][nc]  # 0 or 1
                new_cost = cost + move_cost
                
                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    if move_cost == 0:
                        dq.appendleft((new_cost, nr, nc))  # front
                    else:
                        dq.append((new_cost, nr, nc))  # back
    
    return dist[end[0]][end[1]]

Minimum Obstacle Removals (LeetCode 2290)

Find the path that requires removing the fewest obstacles.

def minimumObstacles(grid: list[list[int]]) -> int:
    """
    LeetCode 2290: 0-1 BFS where moving through obstacle costs 1,
    moving through empty cell costs 0.
    """
    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0
    
    dq = deque([(0, 0, 0)])
    
    while dq:
        cost, r, c = dq.popleft()
        
        if r == rows - 1 and c == cols - 1:
            return cost
        
        if cost > dist[r][c]:
            continue
        
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_cost = cost + grid[nr][nc]
                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    if grid[nr][nc] == 0:
                        dq.appendleft((new_cost, nr, nc))
                    else:
                        dq.append((new_cost, nr, nc))
    
    return dist[rows-1][cols-1]

Dijkstra on Grid

When grid cells have arbitrary non-negative weights (terrain costs, elevation differences), use Dijkstra with a priority queue.

import heapq

def shortest_path_dijkstra_grid(grid: list[list[int]], 
                                 start: tuple, end: tuple) -> int:
    """
    Dijkstra on a weighted grid where grid[r][c] is the cost
    to enter cell (r, c).
    """
    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[start[0]][start[1]] = grid[start[0]][start[1]]
    
    heap = [(grid[start[0]][start[1]], start[0], start[1])]
    
    while heap:
        cost, r, c = heapq.heappop(heap)
        
        if (r, c) == end:
            return cost
        
        if cost > dist[r][c]:
            continue
        
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_cost = cost + grid[nr][nc]
                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    heapq.heappush(heap, (new_cost, nr, nc))
    
    return dist[end[0]][end[1]]

Path with Minimum Effort (LeetCode 1631)

Find a path where the maximum absolute difference in heights between consecutive cells is minimized.

def minimumEffortPath(heights: list[list[int]]) -> int:
    """
    LeetCode 1631: Dijkstra where edge weight is abs height difference.
    Minimize the maximum edge weight along the path.
    """
    rows, cols = len(heights), len(heights[0])
    effort = [[float('inf')] * cols for _ in range(rows)]
    effort[0][0] = 0
    
    heap = [(0, 0, 0)]  # (max_effort_so_far, row, col)
    
    while heap:
        eff, r, c = heapq.heappop(heap)
        
        if r == rows - 1 and c == cols - 1:
            return eff
        
        if eff > effort[r][c]:
            continue
        
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_eff = max(eff, abs(heights[nr][nc] - heights[r][c]))
                if new_eff < effort[nr][nc]:
                    effort[nr][nc] = new_eff
                    heapq.heappush(heap, (new_eff, nr, nc))
    
    return effort[rows-1][cols-1]

Multi-State BFS

Some grid problems require tracking additional state beyond just (row, col). For example, the number of walls broken, keys collected, or whether a special ability has been used.

Shortest Path with K Walls Removable (LeetCode 1293)

def shortestPath(grid: list[list[int]], k: int) -> int:
    """
    LeetCode 1293: BFS with state = (row, col, walls_remaining).
    Can break at most k walls.
    """
    rows, cols = len(grid), len(grid[0])
    
    # Optimization: if k >= rows + cols - 3, we can go straight
    if k >= rows + cols - 3:
        return rows + cols - 2
    
    queue = deque([(0, 0, k, 0)])  # (row, col, walls_left, steps)
    visited = {(0, 0, k)}
    
    while queue:
        r, c, walls_left, steps = queue.popleft()
        
        if r == rows - 1 and c == cols - 1:
            return steps
        
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_walls = walls_left - grid[nr][nc]
                if new_walls >= 0 and (nr, nc, new_walls) not in visited:
                    visited.add((nr, nc, new_walls))
                    queue.append((nr, nc, new_walls, steps + 1))
    
    return -1

Shortest Path with Keys and Doors (LeetCode 864)

def shortestPathAllKeys(grid: list[str]) -> int:
    """
    LeetCode 864: BFS with state = (row, col, keys_bitmask).
    Collect all keys in minimum steps.
    """
    rows, cols = len(grid), len(grid[0])
    start_r = start_c = 0
    total_keys = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '@':
                start_r, start_c = r, c
            elif grid[r][c].islower():
                total_keys += 1
    
    all_keys = (1 << total_keys) - 1
    queue = deque([(start_r, start_c, 0, 0)])
    visited = {(start_r, start_c, 0)}
    
    while queue:
        r, c, keys, steps = queue.popleft()
        
        if keys == all_keys:
            return steps
        
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            
            cell = grid[nr][nc]
            if cell == '#':  # wall
                continue
            
            new_keys = keys
            if cell.islower():  # key
                new_keys |= (1 << (ord(cell) - ord('a')))
            elif cell.isupper():  # door
                if not (keys & (1 << (ord(cell.lower()) - ord('a')))):
                    continue  # don't have the key
            
            if (nr, nc, new_keys) not in visited:
                visited.add((nr, nc, new_keys))
                queue.append((nr, nc, new_keys, steps + 1))
    
    return -1

Algorithm Selection Guide

Condition	Algorithm	Time	Space
All moves cost 1	BFS	O(R*C)	O(R*C)
Moves cost 0 or 1	0-1 BFS	O(R*C)	O(R*C)
Varied non-negative weights	Dijkstra	O(RC log RC)	O(R*C)
Extra state dimensions	Multi-state BFS	O(RCS)	O(RCS)
Multiple sources	Multi-source BFS	O(R*C)	O(R*C)

Where S is the number of possible extra states (e.g., 2^keys, k+1 wall breaks).

Common Pitfalls

1. Marking visited too late: In BFS, mark visited when you add to the queue, not when you dequeue. Otherwise, the same cell gets added multiple times.

2. Using DFS for shortest path: DFS does NOT find shortest paths in unweighted graphs. It finds A path, not the shortest path. Always use BFS.

3. Forgetting extra state dimensions: If breaking a wall changes the optimal path, the state must include walls broken. Just (row, col) is not enough.

4. Off-by-one in grid bounds: Always check 0 {'<='} nr {'<'} rows and 0 {'<='} nc {'<'} cols before accessing grid[nr][nc].

5. Not using 0-1 BFS when applicable: Using Dijkstra for a 0-1 weight grid works but is slower (O(RC log RC) vs O(RC)).

Practice Problems

Problem	Difficulty	Pattern
LeetCode 1091: Shortest Path in Binary Matrix	Medium	Standard BFS
LeetCode 994: Rotting Oranges	Medium	Multi-source BFS
LeetCode 286: Walls and Gates	Medium	Multi-source BFS
LeetCode 2290: Minimum Obstacle Removals	Hard	0-1 BFS
LeetCode 1631: Path with Minimum Effort	Medium	Dijkstra on grid
LeetCode 1293: Shortest Path with Obstacles	Hard	Multi-state BFS
LeetCode 864: Shortest Path to Get All Keys	Hard	Multi-state BFS
LeetCode 1162: As Far from Land as Possible	Medium	Multi-source BFS

Key Takeaways

1. Grids are graphs. Every grid problem is a graph problem with implicit edges to neighbors.
2. BFS = shortest path for unweighted. This is the default algorithm for grid shortest path.
3. 0-1 BFS saves a log factor over Dijkstra when weights are binary.
4. Extra state turns (r,c) into (r,c,state). The visited set must include the full state tuple.
5. Multi-source BFS is just BFS with multiple starting points in the queue, used for “nearest X” problems.