第一百三二章 机器人罗比（下）

“唰唰！”，牛仔从大树上跳下来。

然后，他看见了倒在地上，奄奄一息的小机器人罗比。

“哥们，发生啥事了？”

杨成看了看小机器人，脸上很是诧异。

就在这时，罗比开口了，它的声音很微弱。

“主人...”

“罗比的寻路逻辑被破坏了...”

“想让罗比带你们回家...”

“请先修复...”

杨成听到这里，已经有了些眉目。

这个关卡敢情是考寻路算法啊。

对于要判定地图中两点间的路径，有一种简单粗暴的做法。

使用深度优先遍历！

它的实现方式很简单，但有2点不足：

1.效率低下

2.它找到的路径不一定是最短路径

第二点尤其致命，绕远路白费力气。

所以这个问题应该是寻找图中两点的最短路径。

当前的地图有什么特点？

它并没有“权重”。

对于有权重的地图，寻找最小权重和路径，有一种经典的算法。

迪杰斯特拉最短路径算法。

但这个地图是没有权重的。

事实上，这里也可以应用迪杰斯特拉算法，但效率不高，而且需要大量的额外空间。

怎样找到一种，足够简单，实现方便，而且效率不会很低的最短路径算法呢？

杨成想到了老朋友。

广度优先遍历算法。

这个方法可以做到！

但是，我们得给它做点小小的改变。

-

这个最短路径问题，迪杰斯特拉算法经过优化后的时间效率是o（n*logn），而广度优先遍历是o（n）的，而且迪杰斯特拉需要的额外空间也更多。