路网遍历，一个递增的路。让人头痛的算法 ( 积分: 100 )

靴

靴子

Unregistered / Unconfirmed
GUEST, unregistred user!
我要在路网中以一个端点为出发点，然后寻找100公里之内的道路，怎么搞这个算法啊？一个端点可能有多条路和他相连，这样分出去，到最后路的情况太多了，而且路又是相通的。我感觉太难了。有朋友说个算法吗？


比如说我从a点出发，到b点，从b点出去的路有10条路，而且从a到b在到这十条路中任何一个都不到我要求的长度呢。这十条路每条又可能分出10条或更多，有些路又可能回到了b点，这样下去，走的路的可能性是成倍增长的。有高手说说这样如何实现效率会高呢？
 
我要在路网中以一个端点为出发点，然后寻找100公里之内的道路，怎么搞这个算法啊？一个端点可能有多条路和他相连，这样分出去，到最后路的情况太多了，而且路又是相通的。我感觉太难了。有朋友说个算法吗？


比如说我从a点出发，到b点，从b点出去的路有10条路，而且从a到b在到这十条路中任何一个都不到我要求的长度呢。这十条路每条又可能分出10条或更多，有些路又可能回到了b点，这样下去，走的路的可能性是成倍增长的。有高手说说这样如何实现效率会高呢？
 
遍历用深度优先或广度优先算法.
求各顶点间的最短路径用Dijkstra算法.
 
我不用求最短距离的。我只想把所有符合的路选出来
 
应该没有这样的算法，因为就算只有一个点不同也算一条不同的线路啊，这样求出来的线路多数是没有意义的
 
楼主说的出发点100公里以内是指 出发点与到达点的 直线距离吧
那我觉得应该先把 出发点100公里以内的所有点都找出来
接下来怎么做我也不会了
希望对你有帮助吧
 
首先，100公里的定义是什么，是起始点到终止点的最近距离还是直线距离？
你的论述中有一个问题，b--c(假设), c又回到b? 这是回路，是不会计算在内的

如果是最近距离，可以先排除直线距离大于100公里的节点，
然后再进行处理

Dijkstra算法计算两点最短路径
弗洛伊德算法计算图内任意两点最短路径
 
1。线距离不是直线的距离而是道路的实际距离。也不是最短距离，而是所有道路实际距离为100公里的
2。回路有多种，如果是刚刚经过的我认为不应该做为回路，这样就在一条线上画起来没有完了。还有就是同过别的路有回到了（假设起点是b-c）c-d，这样我认为是可以的。因为有些路可能回回环的。
 
你的要求是计算起点a到终点b的所有路线，比如有路径1,2,3
条件是每条路径中所有的路线的长度相加<100
对吧？

如果是这样，就遍历
用广度优先遍历或深度优先遍历，应该可以解决你的问题
 
您必须登录或注册才可回复。

Similar threads

不
电子病历的进展 - 不得闲
回复
0
查看
573
不得闲
不
不
关于Delphi的子类化控件消息淫荡法则之一 - 不得闲
回复
0
查看
550
不得闲
不
不
奇淫怪巧之给Delphi的PrintDialog增加一个页码选定范围打印的Edit - 不得闲
回复
0
查看
704
不得闲
不
不
Delphi中设置条件断点 - 不得闲
回复
0
查看
650
不得闲
不
S
【教程】对 TEvent 的一处增强
回复
0
查看
779
swish
S
顶部