示例工程教程【免费下载链接】materialsBonus materials, exercises, and example projects for our Python tutorials项目地址https://gitcode.com/gh_mirrors/ma/materials点击查看免费下载本篇技术指南以仓库 python-heapq-module 中的配套示例为核心讲解如何利用 Python 标准库heapq模块实现优先队列从而在字符地图上求解从左上角到右下角的最短路径。读完本文后你将掌握 Dijkstra 最短路径算法的 Python 落地写法、字符网格地图的建模方式以及如何改造示例代码支持「禁止斜向移动」「带能量消耗」「加权移动」等规则变体。项目背景一份最短路径求解的配套代码仓库中的 python-heapq-module 目录对应一篇讲解 Pythonheapq模块与优先队列使用方法的教程。整个配套项目非常精简只包含两个文件README.md程序的使用说明、地图修改方法与四条改造练习shortest-path.py完整可运行的示例程序负责解析地图、执行寻路并打印结果。这份示例的独特价值在于它不依赖任何第三方库只用标准库heapq就把「优先队列 贪心扩展」的寻路思想完整呈现出来是理解 Dijkstra 算法与优先队列配合方式的绝佳入门素材。运行示例打印带路径标记的地图程序的使用方式非常简单在项目目录下执行$ python shortest-path.py程序运行后会输出一张地图并用字符标出从左上角到右下角的最短路径。仓库当前默认地图的执行结果是.....X.. ......X.. ...XXXX.. ..... .........其中连成的折线就是从起点(0, 0)到终点(9, 4)的其中一条最短路径。结合 shortest-path.py 的收尾代码可以看到整个流程只有两步path find_path(map) print(show_path(path, map))即「先求路径再绘制路径」非常清晰。地图格式如何定义机器人所处的世界地图本质上是一段由多行字符组成的字符串。在 shortest-path.py 中默认地图定义如下map \ .......X.. .......X.. ....XXXX.. .......... .......... 关于地图格式需要注意以下几点每一行代表地图的一行行首的\是为了避免第一行开头出现换行符字符X表示障碍物机器人不能通过除X之外的任何字符都视为可通行区域使用.作为空白标记可以让地图在终端里更易读起点固定为左上角(0, 0)终点固定为右下角(最后一行最后一个字符, 最后一行行号)。起终点的解析逻辑位于 shortest-path.py 的parse_map()函数中def parse_map(map): lines map.splitlines() origin 0, 0 destination len(lines[-1]) - 1, len(lines) - 1 return lines, origin, destination可以看到终点是根据最后一行的字符数推导出来的因此地图中每一行长度应当保持一致否则终点坐标会与预期不符。修改地图的方法在 shortest-path.py 顶部把赋给map的三引号字符串替换成你自己的地图即可。你可以把地图做得更大、更复杂。修改时只需遵守一条规则用X表示障碍其他字符表示可通行。示例把地图改为一个 7×7 的迷宫map \ ....... .X..X.. .X.XX.. .X..... ..XXX.. ....... ....... 由于is_valid()会根据边界和X双重校验坐标见 shortest-path.py超出行宽、行数的坐标以及落在X上的坐标都会被判为非法因此不用担心越界访问。无解时的异常处理如果障碍物多到让左上角到右下角之间根本不存在任何路径程序会抛出异常。这一逻辑位于 shortest-path.pyif destination in tentative: return tentative[destination] [destination] else: raise ValueError(no path)也就是说当优先队列被清空、但终点仍然没有被收录进certain集合时程序会抛出ValueError(no path)。从算法角度讲这说明起点与终点处于两个互不连通的分量中。算法原理heapq 如何驱动 Dijkstra 寻路要真正理解这份示例需要把find_path()的每一步与 Dijkstra 算法的概念对应起来。整体实现位于 shortest-path.pydef find_path(map): lines, origin, destination parse_map(map) tentative {origin: []} candidates [(0, origin)] certain set() while destination not in certain and len(candidates) 0: _ignored, current heapq.heappop(candidates) if current in certain: continue certain.add(current) neighbors set(get_neighbors(lines, current)) - certain shorter get_shorter_paths(tentative, neighbors, current) for neighbor, path in shorter: tentative[neighbor] path heapq.heappush(candidates, (len(path), neighbor)) if destination in tentative: return tentative[destination] [destination] else: raise ValueError(no path)其核心数据结构与角色如下数据结构类型作用tentative字典键为坐标、值为路径列表记录每个格子当前已知的最短路径步数序列candidates堆列表优先队列按路径长度排序等待被扩展的格子certain集合已经确定最短路径的格子避免重复处理整个循环的执行流程是用heapq.heappop(candidates)弹出当前路径最短的格子若该格子已在certain中则跳过防重复将其加入certain表示它的最短路径已经确定枚举它的邻居排除已在certain中的格子若发现更短的路径则更新tentative并把新候选压入堆中直到终点进入certain或堆被清空。为什么堆里的元素是(len(path), position)注意到压入堆的是元组(len(path), neighbor)。Python 的heapq在比较元组时会先比较第一个元素因此路径长度越小优先级越高堆顶始终是当前步数最少的候选格子。这正是优先队列在最短路径算法中的典型用法——步数在这里充当了「距离度量」。另外由于同一格子在发现更短路径后会被重复压入堆旧记录仍在堆中循环开头用if current in certain: continue来跳过过期记录这是一种很常见的惰性删除写法能避免主动从堆中删除元素的复杂性。邻居枚举默认支持 8 方向移动get_neighbors()通过双层循环生成当前格子周围 8 个方向含斜向的候选坐标见 shortest-path.pydef get_neighbors(lines, current): x, y current for dx in [-1, 0, 1]: for dy in [-1, 0, 1]: if dx 0 and dy 0: continue position x dx, y dy if is_valid(lines, position): yield positiondx、dy分别取-1/0/1共 9 种组合剔除(0, 0)自身后得到 8 个方向再经过is_valid()过滤越界坐标与障碍物最终以生成器形式产出合法邻居。正是这里的 8 方向设定决定了「最短路径」默认允许斜向行走。更短路径的判定get_shorter_paths()负责判断经由当前格子到达邻居是否更优见 shortest-path.pydef get_shorter_paths(tentative, positions, through): path tentative[through] [through] for position in positions: if position in tentative and len(tentative[position]) len(path): continue yield position, path当邻居已有记录且其路径长度不超过新路径时跳过否则产生(neighbor, path)更新。由于本例中每走一步的代价均为 1路径长度就是步数这与 Dijkstra 算法「每次选择当前距离最小的顶点进行松弛」的经典过程完全一致。结果可视化show_path 的字符串技巧show_path()把路径坐标回填到地图字符串中见 shortest-path.pydef show_path(path, map): lines map.splitlines() for x, y in path: lines[y] lines[y][:x] lines[y][x 1 :] return \n.join(lines) \n它的做法是把地图按行拆成字符串列表然后针对路径上的每个(x, y)用切片把该行对应位置的字符替换成。这种「字符串切片替换」的方式无需把地图转成二维列表代码十分紧凑值得在类似的网格可视化场景中借鉴。改造练习修改规则后会发生什么README 末尾给出了四道递进的改造题目见 README.md。这些练习虽然不要求写出答案但结合源码可以给出明确的改造思路作为动手实践的向导。练习 1禁止斜向移动让机器人只能上下左右移动即只保留 4 个方向。改造点在get_neighbors()过滤掉dx与dy同时非零的组合即可for dx in [-1, 0, 1]: for dy in [-1, 0, 1]: if dx 0 and dy 0: continue if dx ! 0 and dy ! 0: continue # 跳过斜向 position x dx, y dy ...更简洁的写法是直接枚举四个主方向[(0, -1), (0, 1), (-1, 0), (1, 0)]。改造后路径会变长因为斜向捷径被禁用了。练习 2只允许向右或向下移动机器人只能从左上走向右下永远不能向左或向上。这同样只涉及get_neighbors()的改动——只保留dx 0 and dy 0且不同时为0的候选。由于运动方向被限制地图中可能直接出现「无解」的情况例如某一行全被X堵死此时程序会按预期抛出ValueError(no path)。练习 3引入能量机制较难要求每走一步消耗能量走到*格子可以补充能量能量耗尽则不能移动。这个改造比前两个复杂得多需要动三处数据结构tentative不能再只存「路径」还要记录到达每个格子时的剩余能量或者把「位置 能量」合并成状态能量语义走一步能量-1经过*格子能量按规则恢复例如2且不超过上限堆的比较如果沿用(len(path), position)那么「路径短但能量耗尽」的方案会被错误地选出来。更合理的设计是让堆元素携带更多状态例如(energy_left, len(path), position)让算法优先保证可行性。注意引入能量后问题性质会变化路径长度最短的不再一定可行因为能量约束引入了「路径质量」的维度这已经接近带约束的最短路径问题。练习 4加权移动挑战要求#不再是障碍而是「耗时两倍」的格子。改造思路很直接把「路径长度」从单纯计步升级为「累计代价」。在get_neighbors()中不再过滤#把is_valid()的障碍判断从X推广到#之外即可或为#单独放行计算路径代价时普通格子步长记为1#格子步长记为2堆元素从(len(path), position)改为(cost, position)其中cost是累计加权代价相应地tentative与get_shorter_paths()的比较基准从len(path)改为cost。完成这一步后算法就从不加权的最短路径推广到了标准的 Dijkstra「带权最短路」这也是heapq优先队列在大规模场景下最常见的用途之一。小结这份配套示例以不到 80 行的代码完整演示了「字符地图建模 优先队列寻路 路径可视化」的全链路是学习heapq模块和 Dijkstra 算法不可多得的微型实战。回顾核心要点地图即字符串用X表示障碍其余字符可通行起点终点固定在左上角与右下角算法即循环find_path()用heapq维护候选格子按路径长度弹出、扩展、松弛直到终点确定或无路可走改造即改邻居与代价四个练习分别对应「限制邻居方向」「引入状态维度」「引入加权代价」改造点高度集中在get_neighbors()、get_shorter_paths()与堆元素的结构上。建议你动手跑一遍 shortest-path.py再依次完成四道改造练习——对优先队列的理解会在亲手修改和调试的过程中显著加深。赞分享示例工程教程【免费下载链接】materialsBonus materials, exercises, and example projects for our Python tutorials项目地址https://gitcode.com/gh_mirrors/ma/materials点击查看免费下载相关推荐LeetCode 505 The Maze II 最短路径全解DFS、BFS 与 Dijkstra 优先队列优化LeetCode 505 The Maze II 最短路径全解DFS、BFS 与 Dijkstra 优先队列优化 导读 本文围绕本仓库 articles/th示例工程教程AlgoNote 算法通关手册0505 迷宫 II 最短距离题解——Dijkstra 优先队列求解滚动球最短路径AlgoNote 算法通关手册0505 迷宫 II 最短距离题解——Dijkstra 优先队列求解滚动球最短路径 本篇是「AlgoNote 算法通关手册」教程文档知识库AlgoNote 算法通关手册LeetCode 0499 迷宫 III —— Dijkstra 优先队列求解字典序最小的最短路径AlgoNote 算法通关手册LeetCode 0499 迷宫 III —— Dijkstra 优先队列求解字典序最小的最短路径 本文是「 算法通关手册 ht教程文档知识库上一篇FLUX.1-dev FP8版本中端显卡用户的AI绘画革命下一篇3个你从未意识到的GitHub社区AI代码审查如何改变你的开发习惯创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考