Python使用深度优先搜索解决迷宫最短路径问题

桃夭

发布时间：2026-10-13| 6人浏览过

原创

本文介绍利用Python实现迷宫最短路径求解的算法示例。通过深度优先遍历（DFS）记录从起点到各点的最短步数，对输入二维数组进行预处理，将障碍与边界标记为-1，通行区域初始化为0。算法在遍历过程中动态更新节点步数，最终输出到达出口的最小步数及完整路径记录，适合Python初学者理解递归与状态更新逻辑。

本文通过一个具体的Python实例，详细讲解如何利用算法解决迷宫路径规划问题，内容包含完整的思路分析与代码实现，供读者参考学习。

问题描述：

给定一个 n 行 m 列的二维数组来代表迷宫地图。其中，数字 0 代表障碍物，无法通行；数字 1 代表可行走的路径。每次移动到相邻的单元格视为消耗 1 步。

解题思路：

采用深度优先遍历（DFS）算法。在遍历过程中，记录从起点到达每一个可达点的最短步数，从而确定最优路径。

初始化测试案例：

1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1

具体处理步骤如下： 1. 在原始迷宫图的四周添加一圈值为 -1 的边界，以防止深度优先遍历过程中发生数组越界。 2. 将图中所有的障碍（原值为0）修改为 -1，将所有可通行的区域（原值为1）修改为 0，以便区分状态。 3. 在遍历过程中，若当前节点值为 0（表示未访问或可更新），则将到达该点的累计步数存储在该节点中；若节点值为 -1（障碍），则跳过不遍历；若计算出的当前步数小于节点内已存储的步数，则更新该节点的值。

修改后的迷宫矩阵：

-1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 0 0 -1 -1 0 -1 0 0 0 -1 -1 0 -1 0 -1 -1 -1 -1 0 -1 0 0 0 -1 -1 0 0 0 -1 0 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1

外围添加的 -1 主要用于在遍历逻辑中作为边界检查，防止程序访问非法索引。

设定迷宫的入口为左上角坐标 (1, 1)，出口为右上角坐标 (1, 5)（基于修改后的矩阵索引）。

Python 核心代码实现：

# -*- coding:utf-8 -*-
def init():
  global graph
  graph.append([-1,  -1, -1, -1, -1, -1,  -1])
  graph.append([-1,  0, 0, -1, 0, 0,  -1])
  graph.append([-1,  0, -1, 0, 0, 0,  -1])
  graph.append([-1,  0, -1, 0, -1, -1,  -1])
  graph.append([-1,  0, -1, 0, 0, 0,  -1])
  graph.append([-1,  0, 0, 0, -1, 0,  -1])
  graph.append([-1,  0, 0, 0, 0, 0,  -1])
  graph.append([-1,  -1, -1, -1, -1, -1,  -1])
#深度优先遍历
def deepFirstSearch( steps , x, y ):
  global graph
  current_step = steps + 1
  print(x, y, current_step )
  graph[x][y] = current_step
  next_step = current_step + 1
  '''
  遍历周围4个点:
    如果周围节点不是-1 说明 不是障碍 在此基础上：
        里面是0 说明没遍历过 我们把它修改成当前所在位置步数加1
        里面比当前的next_step大 说明不是最优方案 就修改它
        里面比当前next_step说明当前不是最优方案，不修改
  '''
  if not(x-1== 1 and y==1) and graph[x-1][y] != -1 and ( graph[x-1][y]>next_step or graph[x-1][y] ==0 ) : #左
    deepFirstSearch(current_step, x-1 , y )
  if not(x == 1 and y-1==1) and graph[x][y-1] != -1 and ( graph[x][y-1]>next_step or graph[x][y-1] ==0 ) : #上
    deepFirstSearch(current_step, x , y-1 )
  if not(x == 1 and y+1==1) and graph[x][y+1] != -1 and ( graph[x][y+1]>next_step or graph[x][y+1]==0 ) : #下
    deepFirstSearch(current_step, x , y+1 )
  if not(x+1== 1 and y==1) and graph[x+1][y] != -1 and ( graph[x+1][y]>next_step or graph[x+1][y]==0 ) : #右
    deepFirstSearch(current_step, x+1 , y )
if __name__ == "__main__":
  graph = []
  init()
  deepFirstSearch(-1,1,1)
  print(graph[1][5])

程序运行输出结果如下：

(1, 1, 0) (1, 2, 1) (2, 1, 1) (3, 1, 2) (4, 1, 3) (5, 1, 4) (5, 2, 5) (5, 3, 6) (4, 3, 7) (3, 3, 8) (2, 3, 9) (2, 4, 10) (1, 4, 11) (1, 5, 12) (2, 5, 13) (2, 5, 11) (4, 4, 8) (4, 5, 9) (5, 5, 10) (6, 5, 11) (6, 4, 12) (6, 3, 13) (6, 2, 14) (6, 1, 15) (6, 3, 7) (6, 2, 8) (6, 1, 9) (6, 4, 8) (6, 5, 9) (6, 2, 6) (6, 1, 7) (6, 1, 5) 12

补充说明：本站还提供了一款基于 JavaScript 实现的无限迷宫游戏，供读者参考交互实现：

在线迷宫小游戏地址： http://tools.jb51.net/games/migong

对 Python 其他技术感兴趣的读者，推荐查阅本站相关专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》以及《Python入门与进阶经典教程》。

希望本文所述的算法示例与代码解析能对读者的 Python 程序设计学习有所帮助。