CODEWITHSUNDEEP
javaalgorithmbreadth-first-search
J. Doe
J. Doe

Reputation: 1341

Why doesn't a BFS guarantee a minimal cost path in this case?

I am solving a question on LeetCode:

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1 (important point).

If input:

[[0,0,0],
 [0,1,0],
 [1,1,1]]

then output:

[[0,0,0],
 [0,1,0],
 [1,2,1]]

The code that I wrote adds all the 0s' locations into a queue and carries out a BFS from each such location in the queue. Unfortunately it times out.

The highly upvoted solution given is like this:

public class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[] {i, j});
                }
                else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || 
                    matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
                queue.add(new int[] {r, c});
                matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
            }
        }

        return matrix;
    }
}

While I do more-or-less understand how it works, I had the following question:

Why do we have to check if matrix[r][c] <= matrix[cell[0]][cell[1]] + 1 - doesn't a BFS guarantee that if the edge costs are equal, then the path it found to a particular node is the shortest? Why do we have to check it then?

Upvotes: 3

Views: 216

Answers (3)

Tanuj Yadav
Tanuj Yadav

Reputation: 1297

The problem can also be easily solved in Nlog(N), where N is the total number of cells in the matrix, using Dijkstra's Algorithm.

The only change that you need to make is, instead of one destination, you will consider all 0's as the destination.

So the initial distance of all the 0's will be zero. Then you can simply proceed with Dijkstra.

Update: Solution posted by you is better as its time complexity is O(N).

Upvotes: 0

Robindar
Robindar

Reputation: 484

This check is performed to ensure that we do not continue processing a path when it will not give a better result.

Your BFS solution is fine, but not efficient enough. By aborting early, you ensure that you do not perform useless operations and thus will not time out.

Upvotes: 2

kfx
kfx

Reputation: 8537

There is no guarantee that matrix[r][c] will be reached by the BFS algorithm only once. In fact, in this problem it will be reached multiple times. The guarantee you're talking about is only in force when matrix[r][c] is reached for the first time.

So, an alternative solution would be to keep another matrix of Boolean values marking whether each cell has been visited or not, and replace the check you mention with !visited[r][c]. However, keeping the extra matrix would require extra memory - that's the reason to prefer the current approach.

Upvotes: 3

Related Questions