路径寻宝 · 最短路径可视化

路径寻宝：亲手把 Dijkstra 与 A* 的差别跑出来

最短路径的两个经典算法，绝大多数人都听过名字，但「A* 比 Dijkstra 快」这句话究竟快在哪里、什么时候不成立，靠读定义很难有体感。这个工具给你一块可以随意画墙的网格，让两种算法在同一张地图上跑一遍，用访问节点数、路径长度和单步展开的顺序，把差别直接摆在眼前。

网格中的每个格子是一个节点，上下左右四个方向相邻的格子之间有一条权值为 1 的边。你在地图上画出的墙会封住相应的连接；点两次格子可以分别指定起点与终点；选定算法后点「运行寻路」，工具会逐节点高亮搜索过程，最后把最短路径整条点亮。

两种算法在做什么

• Dijkstra：一个「不看方向」的算法。它维护一个已确认节点集合，每次取出当前代价最小的节点向外扩展。因为它不做任何方向预判，扩展是各向同性的——不管终点在哪儿，它都会先把周围一圈都探完。
• A*：在 Dijkstra 的基础上加了一项启发式估计。每一步除了看「已经走了多远」（记作 g），还看「离终点大概还有多远」（记作 h），并按 g 加 h 排序扩展节点。终点方向上的节点会被优先处理，于是搜索区域常常呈现为一个朝终点的锥形，而不是一个圆。

本工具使用的启发式是曼哈顿距离，即只累加横向与纵向的格数差，不计对角。在四邻接、边权全为 1 的网格上，曼哈顿距离永远不会超过真实最短距离，这个性质叫「可采纳」，它保证 A* 找到的仍然是最短路径。这条性质有前提：一旦允许斜向移动且斜向边权仍为 1，或者边权不再统一，可采纳性就可能被破坏，A* 的结果就不再保证最优。

怎么用：一张地图的完整操作流程

1. 选工具再落笔。左侧工具栏依次是障碍墙、起点、终点、橡皮。先选「障碍墙」，再在网格上逐个点击画墙；画错了用「橡皮」点掉。
2. 设定起点与终点。点「起点」再点一个格子，点「终点」再点另一个格子。两者不可重合，也不宜贴着边界太近，否则起点或终点被围死时会直接得到不可达的结果。
3. 选网格尺寸与算法。10×10 适合快速试手，14×14 是默认的中等尺寸，20×20 适合看大规模下的差异。算法在下拉里选 Dijkstra 或 A*（曼哈顿）。
4. 控制步速。步速决定每个节点的展开间隔，纯属可视化节奏，不影响算法结果。想看清扩展顺序可以调慢，想看整体进度可以调快。
5. 运行与单步。点「运行寻路」让它一次跑完，点「单步」则一次只展开一个节点，适合在关键节点上停下来观察队列内容。
6. 清理与随机。「清访问与路径」只清掉高亮、保留你的墙和起终点，适合换个算法在同一张图上对照；「清空障碍」把地图恢复成空网格；「随机地图」会重新生成障碍与起终点，用来快速观察不同布局下的表现。

判读流程：三个数字怎么读

报告区给出三个量：路径长度是找到的最短路径经过的格子数，两个算法在可采纳启发式下应当一致；访问节点数是搜索过程中被取出并扩展的节点总数，这是两种算法差别最直观的体现；用时是浏览器实际跑完这一遍所花的时间。

读的时候有一个关键点必须先说清楚：这里的「用时」是端到端的墙钟时间，里面包含了逐步高亮的渲染开销，它随着你设置的步速一起变化。步速调到 50 毫秒一步时，即使算法本身很快，用时也会被拉长。所以比较两个算法时，应该看「访问节点数」和「路径长度」，把用时只当作参考量。

最值得做的对照实验是：固定同一张地图，先跑 Dijkstra 记下访问节点数，再清掉高亮、切换到 A* 重跑。障碍越稀疏，A* 相对省下的节点越多；障碍越密、绕行越远，两者差距会收窄。当启发式几乎不起作用时——比如终点被一大圈墙围住、实际路径要绕行很远——A* 的优势就会明显缩小。

常见错误与关键提醒

• 常见错误一：认为 A* 永远更快。A* 的优势来自启发式提供的方向信息。当真实路径长且绕，A* 的排序优势被削弱；当曼哈顿距离与真实剩余距离差距很大时，优势更小。
• 常见错误二：把「访问节点少」直接等同于「路径更优」。路径质量看的是长度，搜索代价看的是访问节点数。这两件事必须分开读：算法可能访问了很多节点却仍然给出最短路径。
• 常见错误三：用步速调出来的用时去比较算法。可视化节奏会直接进入墙钟时间。要比较运行效率，请对比访问节点数。
• 常见错误四：把墙画在起终点格子上，或让两者重合。这会产生没有定义的情况，工具会给出不可达提示。遇到「不可达」先检查是不是被完全围死，而不是以为算法有 bug。
• 关键提醒：本工具所有边的权值都是 1。这意味着不存在「高速公路更便宜」这类加权情形，也意味着曼哈顿启发式在当前设置下是可采纳的。如果以后改成可变权值，A* 的最优性结论需要重新审视。

边界与局限：这个工具解决不了什么

首先，它是一个单机、单用户、纯前端的可视化工具，不做复杂网络分析、不做多源最短路、不做网络流或匹配类问题。其次，网格是固定的四邻接单位代价图，无法表达加权节点。第三，算法本身的耗时在这个工具里被可视化节奏淹没，因此「用时」这一项只适合看趋势，不适合做算法性能基准。工具的教学价值集中在「扩展顺序」这一条线上，而不是毫秒数。

适用范围：想直观理解 Dijkstra 与 A* 的差别；需要在课堂上或自学中演示最短路径的执行过程；想验证「启发式可采纳时才保证最优」这一结论；想找一个零安装、可反复修改地图的寻路玩具。它不适合作为算法性能评测平台，也不适合用来推断任何与个人能力相关的结论。

结果仅供自我探索与练习，不构成医疗或专业诊断。如果结果让你担心，请联系正规机构的专业人员。