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.
On this page
Java arrays and ArrayDeque.
- Search a grid with a queue to find the fewest moves from the start to the goal around walls.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
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]);
}
}shortest path to G: 5
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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]); }}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
| Step / line | 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 |
Behind the scenes
How Java processes this code
The Java compiler produces bytecode. The JVM loads the class and invokes its main method.
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.