Java: breadth-first search for a shortest path

Search a grid with a queue to find the fewest moves from the start to the goal around walls.

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    String[] grid = {
      "S.#.",
      "..#.",
      "...G",
    };
    int rows = grid.length, cols = grid[0].length();
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) {
      Arrays.fill(row, -1);
    }
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[] {0, 0});
    dist[0][0] = 0;
    int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty()) {
      int[] cell = queue.poll();
      for (int[] move : moves) {
        int r = cell[0] + move[0], c = cell[1] + move[1];
        if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r].charAt(c) != '#' && dist[r][c] < 0) {
          dist[r][c] = dist[cell[0]][cell[1]] + 1;
          queue.add(new int[] {r, c});
        }
      }
    }
    System.out.println("shortest path to G: " + dist[2][3]);
  }
}

Output

shortest path to G: 5

Explanation

State-space search treats a problem as states connected by moves. Breadth-first search explores states in order of their distance from the start, using a first-in, first-out queue. When all moves cost the same, the first time it reaches the goal is a shortest path.

The program stores a distance for every cell, starting at -1 for unvisited. It takes a cell from the queue, tries the four neighbours, and sets each unvisited, open neighbour's distance to one more than the current cell. Marking a cell when it is first added keeps it from being queued twice.

Explore the dry run

Guided walkthroughReady

1import java.util.*;

3class Main {

4 public static void main(String[] args) {

5 String[] grid = {

6 "S.#.",

7 "..#.",

8 "...G",

9 };

10 int rows = grid.length, cols = grid[0].length();

11 int[][] dist = new int[rows][cols];

12 for (int[] row : dist) {

13 Arrays.fill(row, -1);

14 }

15 Deque<int[]> queue = new ArrayDeque<>();

16 queue.add(new int[] {0, 0});

17 dist[0][0] = 0;

18 int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

19 while (!queue.isEmpty()) {

20 int[] cell = queue.poll();

21 for (int[] move : moves) {

22 int r = cell[0] + move[0], c = cell[1] + move[1];

23 if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r].charAt(c) != '#' && dist[r][c] < 0) {

24 dist[r][c] = dist[cell[0]][cell[1]] + 1;

25 queue.add(new int[] {r, c});

26 }

27 }

28 }

29 System.out.println("shortest path to G: " + dist[2][3]);

30 }

31}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The start is at distance 0 and is the only cell in the queue.	`queue = [(0,0)]`	—
Take the oldest cell; cells nearer the start are always handled first.	`queue = [(0,0)]`	—
Each newly found neighbour is one step farther than its parent.	`distance grows by 1 per layer`	—
The goal is first reached after 5 moves, around the wall in column 2.	`dist[2][3] = 5`	shortest path to G: 5

Cost and common mistakes

O(R·C) time and space for a grid with R rows and C columns.

Marking a cell as visited only when it is removed from the queue allows duplicates and wastes time.
BFS is shortest only when every move costs the same. For different costs use Dijkstra's algorithm or A*.

Try it yourself

What does dist[2][3] stay as if the goal is walled in?

Reveal answer and reasoning

It stays -1 because the goal is never reached, which also tells you no path exists.

Java: breadth-first search for a shortest path

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading