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

靴

靴子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-07-20

• #1

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


比如说我从a点出发，到b点，从b点出去的路有10条路，而且从a到b在到这十条路中任何一个都不到我要求的长度呢。这十条路每条又可能分出10条或更多，有些路又可能回到了b点，这样下去，走的路的可能性是成倍增长的。有高手说说这样如何实现效率会高呢？

 

靴

靴子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-07-20

• #2

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


比如说我从a点出发，到b点，从b点出去的路有10条路，而且从a到b在到这十条路中任何一个都不到我要求的长度呢。这十条路每条又可能分出10条或更多，有些路又可能回到了b点，这样下去，走的路的可能性是成倍增长的。有高手说说这样如何实现效率会高呢？

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-07-20

• #3

遍历用深度优先或广度优先算法.
求各顶点间的最短路径用Dijkstra算法.

 

靴

靴子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-07-21

• #4

我不用求最短距离的。我只想把所有符合的路选出来

 

S

shappy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-08-08

• #5

应该没有这样的算法，因为就算只有一个点不同也算一条不同的线路啊，这样求出来的线路多数是没有意义的

 

C

chaos518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-08-08

• #6

楼主说的出发点100公里以内是指 出发点与到达点的 直线距离吧
那我觉得应该先把 出发点100公里以内的所有点都找出来
接下来怎么做我也不会了
希望对你有帮助吧

 

M

mwj9

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-08-10

• #7

首先，100公里的定义是什么，是起始点到终止点的最近距离还是直线距离？
你的论述中有一个问题，b--c(假设), c又回到b? 这是回路，是不会计算在内的

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

Dijkstra算法计算两点最短路径
弗洛伊德算法计算图内任意两点最短路径

 

靴

靴子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-08-13

• #8

1。线距离不是直线的距离而是道路的实际距离。也不是最短距离，而是所有道路实际距离为100公里的
2。回路有多种，如果是刚刚经过的我认为不应该做为回路，这样就在一条线上画起来没有完了。还有就是同过别的路有回到了（假设起点是b-c）c-d，这样我认为是可以的。因为有些路可能回回环的。

 

M

mwj9

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-08-15

• #9

你的要求是计算起点a到终点b的所有路线，比如有路径1,2,3
条件是每条路径中所有的路线的长度相加<100
对吧？

如果是这样，就遍历
用广度优先遍历或深度优先遍历，应该可以解决你的问题