BFS算法Python实现路径错误求助：路径误入障碍格1

你实现的BFS算法输出路径[(0, 1), (0, 2), (1, 2), (2, 2)]并没有误入障碍——对照你给出的矩阵，这条路径上的所有格子值都是0，完全符合“仅允许在值为0的格子移动”的规则。你提到的“正确路径”其实是一条更长的绕路，而BFS的核心特性就是找到最短合法路径，所以当前算法的输出是正确的。

如果你确实希望算法走那条绕路，说明你的矩阵定义和预期不符：你可能原本想让(1,2)（第二行第三列）是障碍（值为1），但现在写成了0。修改这个位置的值后，算法就会自动选择你想要的路径。

修改后的矩阵示例 #

m = [
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],  # 将(1,2)改为1
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

代码逻辑验证 #

你的BFS核心逻辑是正确的：

• 邻居节点判断条件0 <= new_x < rows and 0 <= new_y < cols and matrix[new_x][new_y] == 0 and (new_x,new_y) not in visited严格过滤了障碍和已访问节点
• construct_path函数能正确从前驱字典prev中反向构建路径

如果矩阵确实是你给出的样子，算法输出的最短路径完全符合要求；只有当(1,2)设为障碍时，才会触发绕路的路径。

内容的提问来源于stack exchange，提问作者Jonathan Layduhur