笔趣阁 //www.boquge.com/book/105094/ 为您提供编程之战全文阅读！注册本站用户，获取免费书架，追书更方便！
要将广度优先遍历算法，转变成最短路径的算法，需要在遍历的时候，对地图的每一个节点额外存储两个信息：
1.从起始节点到当前节点的路径长度（非必须）
2.当前节点之前的那个节点（前驱节点）
在遍历的过程中，如果抵达了目标节点，就终止遍历。
最短的路径就是：
目标节点，目标节点的前驱节点，前驱节点的前驱节点......
直到起始节点。
相当于是一个沿着目标节点的前驱链表回溯的过程。
这个实现并不复杂，杨成很快就写完了代码。
但他也注意到了这个算法的不足之处：
消耗的时间比较大，遍历的点会很多。
有没有办法让这个算法变得更加智能呢？
“哎哎呀”，只听见小机器人罗比闷哼了一声。
它骨碌碌地爬起来。
“主人，感谢你修复好了罗比的寻路逻辑”。
“那么，下面开始导航吧！”
只见那罗比耷拉着脑袋，一副沉思的模样。
“确定当前为起始节点...”
“确定检查站为目标节点...”
“寻路算法执行中...”
“请稍候...”
罗比一只手握着手电筒，另一只手托着下巴。
杨成和科勒文则呆呆地看着它。
时间一分一秒地过去了...
罗比这边还是没什么动静。
“我的天哪”，杨成以手扶额。
这就尴尬了！
杨成心里忐忑不安。
就在这时，小机器人身上发生了变故。
只见它头顶冒起一股白烟....
1.从起始节点到当前节点的路径长度（非必须）
2.当前节点之前的那个节点（前驱节点）
在遍历的过程中，如果抵达了目标节点，就终止遍历。
最短的路径就是：
目标节点，目标节点的前驱节点，前驱节点的前驱节点......
直到起始节点。
相当于是一个沿着目标节点的前驱链表回溯的过程。
这个实现并不复杂，杨成很快就写完了代码。
但他也注意到了这个算法的不足之处：
消耗的时间比较大，遍历的点会很多。
有没有办法让这个算法变得更加智能呢？
“哎哎呀”，只听见小机器人罗比闷哼了一声。
它骨碌碌地爬起来。
“主人，感谢你修复好了罗比的寻路逻辑”。
“那么，下面开始导航吧！”
只见那罗比耷拉着脑袋，一副沉思的模样。
“确定当前为起始节点...”
“确定检查站为目标节点...”
“寻路算法执行中...”
“请稍候...”
罗比一只手握着手电筒，另一只手托着下巴。
杨成和科勒文则呆呆地看着它。
时间一分一秒地过去了...
罗比这边还是没什么动静。
“我的天哪”，杨成以手扶额。
这就尴尬了！
杨成心里忐忑不安。
就在这时，小机器人身上发生了变故。
只见它头顶冒起一股白烟....