最短路径问题

mygame · 发表于 2011-11-26 16:37:58

有这样一组房间号
怎么用最短路径把这些房间串起来呢

3250|3281|3267|3280|3266|3279|3265|3278|3264|3263|3276|3272|3271|3275|3268|3273|3270|3274

北大侠客行MUD，中国最好的MUD

littleknife · 发表于 2011-11-26 16:50:38

本帖最后由 littleknife 于 2011-11-26 04:57 PM 编辑

你是要生成，这些房间号的连接路线吗？最短路线是指房间号和房间号间最短？？还是总路线最短？

另外貌似你转cmud啦？不用mush了吗？

mygame · 发表于 2011-11-26 17:15:11

发现3.34的待执行速度不错，用的比较顺手，提供的地图函数比较多，没什么转什么的
就先用用了，最好是总线路最短

littleknife · 发表于 2011-11-26 17:22:35

总线路最短，为什么要经过中间点呢？经过中间点的理解就是选择每一步的最短路线，然后全加上不就成了。

难道是起点到终点的线路先搜索出来，然后再看各个点加在一起的路线是否比那个直接搜索的短？。。不理解。。

zztuzki · 发表于 2011-11-26 17:32:25

经过中间点的顺序任意，总路线最短?

happylife · 发表于 2011-11-26 17:39:17

abcd四个点，起点为a，找出到bcd的最短路径，比如ac，然后走到c，找出c到bd的最短路径，比如cd，得出路径是acdb？俺是外行，不要笑...

littleknife · 发表于 2011-11-26 21:48:19

这个思路是不对的。
A->B A周围点最短的路线如果是3步，
B->C B周围点最短的路线如果是2步,
C-D C周围点最短的路线如果是2步,

按上面的逻辑：A->D等于3+2+2=7步。

可是有下面情况：
A->D如果直接是5步，但却不是A周围最短的路线（3步），可是A->D的最短路线实际是直接A->D，5步。

happylife · 发表于 2011-11-26 22:27:46

本帖最后由 happylife 于 2011-11-26 10:35 PM 编辑

想法不成熟，编辑掉

littleknife · 发表于 2011-11-26 22:31:48

回复 8# happylife

所以说，楼主的意思一直不明白。。没看懂啥意思呢。。

alucar · 发表于 2011-11-26 23:01:38

遍历？

		自动登录	找回密码
密码			注册