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

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.net/201310378.html

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