设为首页收藏本站|繁體中文

开启辅助访问

Project1»广场 › 技术讨论 › 综合技术讨论区 › RPG Maker 技术区 › 【算法】Dijkstra寻路算法在RM地图上的应用 ...

发新帖

查看: 4101|回复: 8

上一主题

下一主题

[RMXP发布] 【算法】Dijkstra寻路算法在RM地图上的应用

梦石: 0
星屑: 2744
在线时间: 2630 小时
注册时间: 2013-1-16
帖子: 5657

发消息

1楼

发表于 2014-11-27 20:29:05 | 显示全部楼层

本帖最后由 myownroc 于 2014-11-27 20:38 编辑

我的循环多一层的原因是我用了两个变量(ij)对地图的点进行遍历，如果改成一个自然就少了一层。而且我没有用队列来储存点，用的是二维数组，这样效率低了一点(回头弄个队列的来玩玩)。ps:我怎么觉得你的循环只有一层?

Dijkstra对图的权有所判断，而BFS没用到，所以这个Dijkstra像BFS。
另外当起点终点同在一集合就可以退出循环了吧?

点评

听说数组的实现是两头延长，shift也能O(1)吧发表于 2014-11-28 20:39

就这样吧，我就不造队列模型了，其实用数组可以造队列模型，不过有些麻烦就是了发表于 2014-11-27 21:04

这个是数组，删除第一个成员不会向队列/链表那样改一下头节点指针就完了，后面其他成员的下标也要改变，所以应该要有一个循环。发表于 2014-11-27 20:58

不知道shift是如何实现的，正常来讲删除队列头部的复杂度是O(1)，如果用的循环队列的话。其实这个东西优化效果比较明显发表于 2014-11-27 20:48

我知道为什么我感觉你只有一层循环了:queue.shift隐含了一层循环，实际上你的循环也是两层。发表于 2014-11-27 20:45

评分

参与人数 1	星屑 +60	收起理由
RyanBern	+ 60	塞糖

查看全部评分

(Created by @喵kano)

施工现场：hotege.github.io

回复支持反对

使用道具举报

发新帖

站长信箱：[email protected]|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2024-5-17 10:20

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表