主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
以起点为首节点开始分支,分支的个数就是当前节点有几个位置可以走,节点内容为当前所在迷宫位置 就这样不停的分支,每生成一个节点就判断是否为终点位置,是则得出结果, 输出路径。因为生成的树的层数对应的正是已走的步数,所以第一个结果必是最短的 另外在数据结构上可以多设计一个数组记录已经走过的位置,当生成的节点位置已经被走过,则可删除该节点, 这样可以减少搜索次数。 这是类似的广度搜索,如果数据量不多,用递归会更直观,简单。
用户登录
还没有账号?立即注册
用户注册
投稿取消
文章分类: |
|
还能输入300字
上传中....