一个类似地图寻路径的例子

JavaScript 2013-10-22 地图,路径,节点,mxGraph

这两天,哈尔滨雾霾让我感到很不习惯,雾都迁移了。每天打开空气质量检测,还是发现箭头指向橙色或红色块,雾都还是雾都。。。

先贴出DEMO http://www.qttc.net/static/demo/mxgraph/search/

寻路径...是一个极其复杂的算法应用,但也可以这么简单的一句话概括:找到触发点至目标点之间最短的路径。大家应该有过在地图上搜索某个地方怎么走,然后地图程序会给出一条“合理路线”仅供参考,我今天要给大家讲的这个跟地图类似,但又跟地图不同。

地图:

例子程序:

从例子程序中我们可以看出有很多个节点,类似地图上的不同地点,每个节点都被一条或多条线条连接,类似地图上的道路,不同的是地图上的道路可能是弯曲的,而例子中的线条都是直线的。

寻短路径

要完成这个功能,你首先要能利用递归功能把所有可能的路径都走一遍并记录下来,然后你才能知道哪一条路径是捷径。这里的逻辑相对有点绕,没接触过这样折腾人的业务处理真是要花点时间好好屡屡思维。因为稍微不留神就又可能走入死胡同。

比如程序可能这样走:

d点 有两条边,分别通向 b,f。

走b方向,b方向有两条边,分别通向 e,d

走d方向,d点有两条边,分别通向 b,f。

走b方向 ...

或者a点到i点的程序走法也可能会这样陷入死胡同:

a -> b

b -> d

d -> f

f -> e

e -> b

b -> d

...

因此,在递归过程中,你需要巧妙的判断处理,我的核心Code直接就贴出来,大家可以看看实例中的Code,同时在调试递归这种程序时是非常痛苦的,即使你使用断点功能一步一步的跟也有可能会跟迷糊,常常不知道已经进入第几层递归了,然后可能重新开始调试。

文字链接:《一个类似地图寻路径的例子

文章地址:http://www.qttc.me/201310378.html

除非标注,琼台博客所有博文均为原创,转载请加文字链接注明来源

乳名?小名?昵称?网名?均可

email,放心,我不会给你乱投广告的

想获得回访就把你的站点URL写上(没有留空)

[NOTICE]木要投放广告
[NOTICE]木要骂人,说不该说的话
[NOTICE]自由言论,但要遵纪守法

Comments 2

  • 大侠,请问“一个类似地图寻路径的例子” 的源代码还有吗?能让我参考一下吗,我找了好久相关的例子,都没有找到。我要做一个类似的在地图图片上找最短路线的程序。先谢谢了
    2016-04-21 04:22:40 [ 跟帖 ]
    地图寻路与我这个是有差别的,地图是有方位,而我这个是要穷举所有!!
    2017-03-10 09:16:22 [ 跟帖 ]
    1 #