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

Question

我正在解决关于LeetCode的问题：

给定矩阵由0和1组成，找到每个单元格最近的0的距离。两个相邻单元之间的距离为1（重要点）。 如果输入：

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

然后输出：

[[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

无法保证BFS算法只能到达一次matrix[r][c]。事实上，在这个问题上，它将达到多次。你所谈论的保证只有在第一次达到matrix[r][c]时才有效。

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

Answer 2

执行此检查以确保在不能提供更好结果时不继续处理路径。

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

Answer 3

在Nlog（N）中也可以很容易地解决这个问题，其中N是矩阵中的单元总数，使用Dijkstra算法。 您需要做的唯一更改是，而不是一个目的地，您将所有0都视为目的地。 因此，所有0的初始距离将为零。然后你可以简单地继续Dijkstra。 更新：您发布的解决方案更好，因为其时间复杂度为O（N）。