如何用BFS算法求解网格中两点间的全部最短路径

不需要更换其他算法，调整传统BFS的已访问标记逻辑即可实现全最短路径查找，路径遗漏问题本质是传统单最短路径BFS的标记规则不适用多路径场景。

传统BFS查找单条最短路径时，节点第一次被遍历到的路径长度，就等于起点到该节点的最短距离，因此直接将节点标记为永久已访问、禁止后续分支进入，既能保证路径最短，也能提升遍历效率。
但查找全部最短路径时，同一节点可能被多条等长的最短路径抵达。以给出的3*3网格为例：

• 节点4到起点0的最短距离是2
• 路径0->1->4长度为2，属于最短路径分支
• 路径0->3->4长度同样为2，也属于最短路径分支
  如果在第一次遍历到节点4时就将其标记为永久不可访问，后续0->3分支就无法进入节点4，自然会漏掉合法路径。

把全局永久已访问标记，替换为「最短距离表+层差判断」逻辑即可，具体步骤：

1. 预计算最短距离表
   先从起点跑一次基础BFS，记录起点到每个节点的最短路径长度，存入dist[]数组。以3*3网格为例，dist[0]=0，dist[1]=dist[3]=1，dist[2]=dist[4]=dist[6]=2，dist[5]=dist[7]=3，dist[8]=4，和实际最短路径长度一致。
2. 带约束遍历路径
   从起点开始做回溯式遍历，每一步访问邻接节点时，不再依赖全局已访问标记做拦截，仅当邻接节点满足dist[邻接节点] == dist[当前节点] + 1时，才允许进入该节点。
3. 记录结果+回溯
   遍历过程中维护当前路径列表，走到终点时就将当前路径存入结果集；递归/回溯返回时，将当前节点从路径列表中移除，避免影响其他分支遍历。

这个逻辑不会出现绕路、走回头路的问题：往回走的节点距离一定比当前节点距离小1，不满足层差判断条件，会被直接过滤，不会产生无效遍历。

按照这个逻辑处理节点4的场景：当遍历0->1分支到节点4时，dist[4] = dist[1]+1 = 2，符合准入条件；后续遍历0->3分支到节点4时，dist[4] = dist[3]+1 =2，同样符合准入条件，不会被拦截，0->3->4相关的合法路径就不会被遗漏。

不需要改用纯DFS等其他算法：

• 无约束的纯DFS会遍历大量长度超过最短路径的无效分支，效率远低于调整后的BFS
• 带距离约束的DFS核心判断逻辑和上述方案一致，但BFS按层扩展的特性天然匹配最短路径的长度规则，实现逻辑更直观，无效遍历更少

针对3*3网格测试用例，调整后的BFS可以准确输出全部6条最短路径：

• 0->1->2->5->8
• 0->1->4->5->8
• 0->1->4->7->8
• 0->3->4->5->8
• 0->3->4->7->8
• 0->3->6->7->8

内容的提问来源于stack exchange，提问作者Harry Kim