Dart实现网格矩阵两点最短路径BFS算法异常排查

• 首先验证BFS基础实现逻辑：BFS依赖队列的先进先出特性保证逐层遍历，才能得到最短路径，首先检查队列的出队操作是否正确。
• 其次验证路径记录逻辑：BFS遍历过程中需要记录每个节点的前驱节点，才能在找到终点后回溯得到完整路径，检查是否有相关逻辑实现。
• 最后验证边界、障碍物校验逻辑是否符合需求。

1. 队列出队操作错误：代码中使用queue.removeLast()取出元素，该操作是从队尾取元素，把队列当成了栈使用，实际实现的是DFS而非BFS，无法保证得到最短路径，应该改为queue.removeFirst()从队头取元素。
2. 缺失路径回溯逻辑：你找到终点后直接把当前待遍历的队列赋值给solution输出，队列中存储的是还未处理的待遍历节点，根本不是从起点到终点的路径，完全不符合逻辑。需要额外记录每个节点的前驱节点，找到终点后从终点反向遍历到起点，再反转得到正序路径。

import 'dart:collection';

class Point {
  int x;
  int y;
  Point? parent; // 新增前驱节点属性用于回溯路径
  Point({required this.y,required this.x, this.parent});
}

void main() {
  print('Finding a viable solution for the shortest path...');
  
  var grid = [
    ['🌿','🌿','🌿','🌿','🌿'],
    ['🌿','🌿','🌿','🌿','🌿'],
    ['🌊','🌿','🌊','🌿','🌿'], // 起点 (y=2,x=1)
    ['🌿','🌿','🌊','🌿','🌿'], // 终点 (y=2,x=3)
    ['🌿','🌿','🌿','🌿','🌿'],
  ];
  
  var characterPosition = Point(y: 2, x: 1);
  var characterDestination = Point(y: 2, x: 3);
  
  PathFinder pathFinder = PathFinder(grid, characterPosition, characterDestination);
  if (pathFinder.solutionExists) {
    print('...Solution exists!');
    for (Point point in pathFinder.solution) {
      print('(${point.y},${point.x})');
    }
  }
  else {
    print('...No solution exists.');
  }
}

class PathFinder {
  late Queue<Point> solution;
  late bool solutionExists;

  PathFinder(grid, characterPosition, characterDestination) {
    Queue<Point> queue = Queue<Point>();
    queue.add(Point(y: characterPosition.y, x: characterPosition.x));

    List<List<bool>> visited = List.generate(
      grid.length,
      (index) => List.generate(
        grid[0].length,
        (index) => false,
        growable: false,
      ),
      growable: false,
    );

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

    while (queue.isNotEmpty) {
      Point point = queue.removeFirst(); // 改为从队头取元素，恢复BFS逻辑

      // 找到终点
      if (point.x == characterDestination.x && point.y == characterDestination.y) {
        solutionExists = true;
        // 回溯构建路径
        solution = Queue<Point>();
        Point? current = point;
        while(current != null) {
          solution.addFirst(current); // 从终点往起点加，用addFirst保证最终顺序是起点到终点
          current = current.parent;
        }
        return;
      }

      // 上
      if (_isValid(x: point.x, y: point.y - 1, grid: grid, visited: visited)) {
        queue.add(Point(y: point.y - 1, x: point.x, parent: point));
        visited[point.y - 1][point.x] = true;
      }

      // 下
      if (_isValid(x: point.x, y: point.y + 1, grid: grid, visited: visited)) {
        queue.add(Point(y: point.y + 1, x: point.x, parent: point));
        visited[point.y + 1][point.x] = true;
      }

      // 左
      if (_isValid(x: point.x - 1, y: point.y, grid: grid, visited: visited)) {
        queue.add(Point(y: point.y, x: point.x - 1, parent: point));
        visited[point.y][point.x - 1] = true;
      }

      // 右
      if (_isValid(x: point.x + 1, y: point.y, grid: grid, visited: visited)) {
        queue.add(Point(y: point.y, x: point.x + 1, parent: point));
        visited[point.y][point.x + 1] = true;
      }
    }

    solutionExists = false;
    solution = Queue();
    return;
  }

  bool _isValid({required int x, required int y, required List<List<String>> grid, required List<List<bool>> visited}) {
    if (x >= 0 && y >= 0 && x < grid[0].length && y < grid.length && grid[y][x] != '🌊' && visited[y][x] == false) {
      return true;
    }
    return false;
  }
}

Finding a viable solution for the shortest path...
...Solution exists!
(2,1)
(1,1)
(1,2)
(1,3)
(2,3)

对应的移动方向为：上→右→右→下，符合预期的最短路径。

内容的提问来源于stack exchange，提问作者Josh Kautz