为什么 BFS 在这种情况下不保证最小成本路径？

Question

我正在解决 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]]

我写的代码将所有0s的位置添加到队列中，并从队列中的每个这样的位置执行BFS。不幸的是它超时了。

给出的高度赞成的解决方案是这样的：

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;
    }
}

虽然我或多或少地了解它是如何工作的，但我有以下问题：

为什么我们必须检查 matrix[r][c] <= matrix[cell[0]][cell[1]] + 1 - BFS 不保证 如果边成本相等，那么它找到的到特定节点的路径是最短的?那为什么还要检查呢？

Answer 1

不保证 matrix[r][c] 只会被 BFS 算法达到一次。事实上，在这个问题中，它将达到多次。您所说的保证仅在首次达到 matrix[r][c] 时有效。

因此，另一种解决方案是保留另一个 Boolean 值矩阵，标记每个单元格是否已被访问，并将您提到的检查替换为 !visited[r][c]。然而，保留额外的矩阵需要额外的内存 - 这就是更喜欢当前方法的原因。

Answer 2

执行此检查是为了确保我们不会继续处理无法提供更好结果的路径。

您的 BFS 解决方案很好，但效率不够高。通过提早中止，您可以确保不会执行无用的操作，因此不会超时。

Answer 3

问题也可以在Nlog(N)中轻松解决，其中N是矩阵中的单元格总数，使用Dijkstra算法。

您需要做的唯一更改是，您将将全 0 视为目的地，而不是一个目的地。

所以所有0的初始距离都为零。然后你可以简单地继续使用 Dijkstra。

更新： 你发布的解决方案更好，因为它的时间复杂度是 O(N).

为什么 BFS 在这种情况下不保证最小成本路径？

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

java

algorithm

breadth-first-search