How to list a path using the BFS algorithm?

Question

Java

Good day!
I'm using a breadth-first search algorithm to find the shortest path in a two-dimensional array. Works correctly,
but I can't get the path from source to destination as a queue or list.

public class SearchMazeBFS {

    private static final int ROW = 9;
    private static final int COL = 10;
    private int[] rowNum = new int[] { -1, 0, 0, 1 };
    private int[] colNum = new int[] { 0, -1, 1, 0 };

    private static class Point {
        private Point(int row, int col) {
            this.x = row;
            this.y = col;
        }

        private int x;
        private int y;
    }

    private static class QueueNode {
        private QueueNode(Point src, int d) {
            this.pt = src;
            this.dist = d;
        }

        private Point pt;
        private int dist;
    }

    private boolean isValid(int row, int col) {
        return (((row >= 0) && (row < ROW)) && ((col >= 0) && (col < COL)));
    }

    private int BFS(int mat[][], Point src, Point dest) {
        if ((mat[src.x][src.y] == 0) || (mat[dest.x][dest.y] == 0))
            return Integer.MAX_VALUE;

        boolean[][] visited = new boolean[ROW][COL];

        visited[src.x][src.y] = true;

        Queue<QueueNode> q = new ArrayDeque<>();

        QueueNode s = new QueueNode(src, 0);
        q.add(s);

        while (!q.isEmpty()) {
            QueueNode curr = q.peek();
            Point pt = curr.pt;

            if (pt.x == dest.x && pt.y == dest.y) {
                return curr.dist;
            }

            q.poll();

            for (int i = 0; i < 4; i++) {
                int row = pt.x + rowNum[i];
                int col = pt.y + colNum[i];

                if ((isValid(row, col) && mat[row][col] == 1)
                        && !visited[row][col]) {
                    visited[row][col] = true;
                    QueueNode adjCell = new QueueNode(new Point(row, col),
                            curr.dist + 1);
                    q.add(adjCell);
                }
            }
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        SearchMazeBFS smbfs = new SearchMazeBFS();
        int[][] mat = new int[][] {
                { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
        };

        Point source = new SearchMazeBFS.Point(0, 2);
        Point dest = new SearchMazeBFS.Point(2, 0);

        int dist = smbfs.BFS(mat, source, dest);

        if (dist != Integer.MAX_VALUE)
            System.out.println("Shortest Path is " + dist);
        else
            System.out.println("Shortest Path doesn't exist");
    }
}

Answer 1

It is necessary to store the previous one for each vertex. Write this value down when you put the vertex in the queue. For the top (row, col) you have the previous one in the code (pt.x, pt.y).
After, when you have found the distance to the final vertex, you can create an array of this length and fill it from the end. We need a pointer that points to the end vertex. Move it to the previous one for the current vertex until you reach the beginning or a known number of steps (distance already found).

Answer 2

Instead , you need to do this:

static final byte DIR_UNKNOWN = 0;
static final byte DIR_UP = 1;
...

byte[][] bestDirection = new boolean[ROW][COL];  // изначально заполнено DIR_UNKNOWN

for (int dir = DIR_UP; dir <= DIR_RIGHT; ++dir) {
  ...
  bestDirection[row][col] = dir;
}

When we reach the finish line, we do the opposite. Namely: we determine what is the bestDirection at the finish line, and if it is, for example, DIR_UP, we shift down by 1. And so on, until we get to the start.
If there are many finishes, it might be better to start with them, adding them to the queue in random order. And then, when the search gets to the start, make a reverse move.