爱看小说网

繁体版 简体版
爱看小说网 > 编程之战 > 第一百三三章 最短路径

第一百三三章 最短路径

章节错误,点此举报(免注册),举报后维护人员会在两分钟内校正章节内容,请耐心等待,并刷新页面。

要将广度优先遍历算法,转变成最短路径的算法,需要在遍历的时候,对地图的每一个节点额外存储两个信息:    1.从起始节点到当前节点的路径长度(非必须)    2.当前节点之前的那个节点(前驱节点)    在遍历的过程中,如果抵达了目标节点,就终止遍历。    最短的路径就是:    目标节点,目标节点的前驱节点,前驱节点的前驱节点......    直到起始节点。    相当于是一个沿着目标节点的前驱链表回溯的过程。    这个实现并不复杂,杨成很快就写完了代码。    但他也注意到了这个算法的不足之处:    消耗的时间比较大,遍历的点会很多。    有没有办法让这个算法变得更加智能呢?    “哎哎呀”,只听见小机器人罗比闷哼了一声。

『加入书签,方便阅读』