第一百三三章 最短路径（1/2）

要将广度优先遍历算法，转变成最短路径的算法，需要在遍历的时候，对地图的每一个节点额外存储两个信息：

1.从起始节点到当前节点的路径长度（非必须）

2.当前节点之前的那个节点（前驱节点）

在遍历的过程中，如果抵达了目标节点，就终止遍历。

最短的路径就是：

目标节点，目标节点的前驱节点，前驱节点的前驱节点......

直到起始节点。

相当于是一个沿着目标节点的前驱链表回溯的过程。

这个实现并不复杂，杨成很快就写完了代码。

但他也注意到了这个算法的不足之处：

消耗的时间比较大，遍历的点会很多。

有没有办法让这个算法变得更加智能呢？

“哎哎呀”，只听见小机器人罗比闷哼了一声。

它骨碌碌地爬起来。

“主人，感谢你修复好了罗比的寻路逻辑”。