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

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

难道是 起点到终点的线路先搜索出来,然后再看各个点加在一起的路线是否比那个直接搜索的短?。。不理解。。{:7_274:}

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

遍历?
页: [1] 2
查看完整版本: 最短路径问题