DFS不保证最短路径，因其按单一方向深入可能先找到长路径；需遍历所有路径、回溯更新最小步数并剪枝才能求得最短路径。
深度优先搜索（DFS）本身不保证找到最短路径，但它可以用来求解迷宫中是否存在路径、所有可行路径，或在加限制条件下逼近最短路径。真正求“严格最短路径”时，广度优先搜索（BFS）更自然、更高效。但若必须用 DFS 实现最短路径，核心思路是：**遍历所有从起点到终点的路径，记录并更新最小步数**。
为什么 DFS 默认不直接给出最短路径
DFS 沿一个方向“钻到底”，再回溯尝试其他分支，路径长度高度依赖探索顺序。它可能先找到一条绕远的路径，而更短的路径藏在后面才被访问。因此，单纯首次到达终点就返回，结果往往不是最短的。
用 DFS 求最短路径的关键操作
需要配合回溯与全局最优更新机制：
-
维护一个全局最小步数变量（如
min_step = float('inf')），每次成功抵达终点时更新 -
递归中传入当前步数（
step），每走一格 +1 -
设置剪枝条件：若当前
step ≥ min_step，直接返回，避免无效深入（重要优化） -
使用访问标记数组（
visited）防止循环；回溯时要还原标记（即“撤步”） - 四个方向按固定顺序尝试（如右→下→左→上），确保覆盖全部可能
典型代码结构（Python 示例）
假设迷宫为二维列表 grid，0 为空地，1 为障碍，起点 (sx, sy)，终点 (ex, ey)：
if x == ex and y == ey:
nonlocal min_step
min_step = min(min_step, step)
return
if step >= min_step: # 剪枝：不比已知更优就停
return
for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
nx, ny = x + dx, y + dy
if 0 visited[nx][ny] = True
dfs(nx, ny, step + 1)
visited[nx][ny] = False # 回溯还原
实际使用中的注意事项
DFS 求最短路径适合小规模迷宫（如 ≤ 20×20）：
- 时间复杂度最坏为
O(4^(n×m))，无剪枝会指数爆炸 - 递归深度大时需调高 Python 的递归限制，或改用显式栈避免栈溢出
- 若只需判断“是否可达”，DFS 效率高；若明确要“最短步数”，优先选 BFS
- 想同时输出最短路径本身？可在递归中维护一个路径列表，抵达终点时拷贝保存
