Breadth-first search

Breadth-first search starts at a source node, visits all its neighbours, then all their unvisited neighbours, and so on. It uses a first-in, first-out queue, so every node at distance 1 is processed before any node at distance 2.

That ordering gives BFS its key property: in an unweighted graph (or one where every edge has the same cost) the distance at which BFS first discovers a node is the length of the shortest path to it. This makes BFS the default tool for minimum number of steps, moves or hops.

BFS visits each vertex and edge at most once, so it runs in O(V + E) time with O(V) space for the queue and the visited set. On a grid of R by C cells, that is O(R x C).

1. 1Put the source in a queue with distance 0 and mark it visited.
2. 2Pop the front node. If it is the target, its distance is the answer.
3. 3For each neighbour that is not visited, mark it visited immediately, set its distance to the current distance + 1, and push it.
4. 4Repeat until the queue is empty. Nodes never reached are unreachable.
5. 5To process level by level (for example to count minutes or layers), read the queue length at the start of each round and pop exactly that many nodes.
6. 6For multi-source BFS, push all starting nodes with distance 0 at the beginning; the expansion then gives each node its distance to the nearest source.

from collections import deque

def shortest_path(grid, start, target):
    # grid cells: 0 = open, 1 = wall; start and target are (row, col)
    rows, cols = len(grid), len(grid[0])
    q = deque([(start, 0)])
    seen = {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == target:
            return d
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == 1 or (nr, nc) in seen:
                continue
            seen.add((nr, nc))        # mark when pushed, not when popped
            q.append(((nr, nc), d + 1))
    return -1                         # target unreachable

Each cell enters the queue at most once because it is marked as seen when pushed. The first time the target is popped, d is the fewest moves. Time and space are O(rows x cols).

Cost: O(V + E) time and O(V) space. On a grid: O(R x C) for both.