BFS on a grid: layers of discovery

Queue discipline buys shortest paths

Breadth-first search explores an implicit graph in layers: first all cells at distance 1 from the start, then all at distance 2, and so on. On an unweighted grid this means the first time BFS touches a cell, it has discovered a shortest-step path from the start to that cell. That property is a direct consequence of processing cells in FIFO order.

int shortest(int[][] grid, int[] start, int[] goal) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, -1);

    Deque<int[]> q = new ArrayDeque<>();
    q.add(start);
    dist[start[0]][start[1]] = 0;

    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    while (!q.isEmpty()) {
        int[] c = q.poll();
        if (c[0] == goal[0] && c[1] == goal[1]) return dist[c[0]][c[1]];
        for (int[] d : dirs) {
            int nr = c[0] + d[0], nc = c[1] + d[1];
            if (nr<0||nc<0||nr>=rows||nc>=cols) continue;
            if (grid[nr][nc] == 1 || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[c[0]][c[1]] + 1;
            q.add(new int[]{nr, nc});
        }
    }
    return -1;
}

Why FIFO is the secret

Enqueueing neighbors and processing the queue head-first guarantees that no cell is explored before every cell one step closer to the start has been processed. That means the distance written when we first see a cell is minimal — no later path can do better. Changing the queue to a stack gives you DFS, which finds some path, not a shortest one.

Open interactive lab →