高手帮我想想一个经典算法，谢谢了

在一个地图上建有网状的高速公路，沿高速公路分布着许多收费站，其中有些收费站是主副站方式的，两条高速公路的互通区我们称为枢纽，在枢纽与枢纽之间可能存在多条路径。现在要设计一个算法，求出：1、路网上每两个收费站间的最短距离及路径；
2、路网上每两个收费站间与最短距离小于1.3倍的所有路径

1容易，难度在2，可是如果用穷举法根本不可能，1中间可以经过1~n-2个点到n ，时间复杂度n!的
比指数的还大，20左右的就根本算不动了，我想了概率算法~，可是又没办法求出所有路径

19 个解决方案

#1

各位高手帮我出出注意啊

#2

题目都看不懂,楼主能不能写得通俗一些?

#3

穷举搜索带上剪枝又如何？
例如：
想从1到n
当从1走到3，路程已经大于或等于1.3倍最短距离，此时就不必往下走了

#4

同意楼上的，用带剪枝的回溯法求，不过速度也不会提高多少。有必要求出所有的吗？

#5

客户要求啊
有没有更优的算法啊

#6

请教高手啊

#7

犷顶

#8

如果符合要求的路径就是有n！这么多怎么办？
搞不懂与最短距离小于1.3倍的所有路径求出来干吗的，还要列出所有的。

#9

可以考虑利用1中的结果,
设MinDis(A, B) 表示 A, B 两站的最短距离, 由于1中的结果, 现在对于任意A, B, MinDis(A,B)为已知
则求 A, B 两站中满足2的所有路径时, 首先可以使用如下方式排除一些点
考虑站C, 如果 MinDis(A,C) + MinDis(B,C) > 1.3 * MinDis(A, B)
则C站可以被排除, 这样, 就可以在较少的站中再求所有路径

#10

谢谢提供思路，能够给点代码参考下吗

#11

可以参考网络中的路由算法

#12

第二个问题可以看做最短路径的演变，即求<1.5倍最短路径的其他Ｍ个最短路径
假设存在一个第二最短路径满足条件，显而易见，第一最短路径上至少有一条路径不在第二最短路径上，否则两个路径重合．所以可以枚举第一最短路径上的每一条边，每次删除一条，然后求新图的最短路径，取这些最短路中最短的一条就是第二最短路径．有这个算法也很容易构造求第三．．．第Ｍ（最长的一条满足＜１．５倍最短路径的路径）路径．

#13

可以参照一下运筹学里面的《货郎担问题》。。。
具体算法忘记了，等我想想.

#14

慢慢算有什么关系,只要算出一次就好了嘛,反正路又不会变来变去.

#15

遗传算法+贪婪法

#16

K路由嘛，简单

#17

首先Floyd算法算出每对节点的最短距离，时间复杂度O(n^3)，不知道能否接收。
记为MinDistanceMatrix[][];当然你也得到了要计算的source和destination的
最短距离，设为MinDistance, MinDistance = MinDistanceMatrix[source][destination]。

再做一次A*算法：当扩展新的节点时，f(s, d) = g(s, i) + h(i, d)，
令h(i, d) = MinDistanceMatrix[i][d];如果这样计算得出的
f > 1.3*MinDistance, 节点i不会被放入OPEN表中。所以OPEN表中的节点一定是某条
符合条件的路径上的点。让算法结束的条件变为OPEN表为空(原先是找到destination就结束)。
这样能搜索出所有符合条件的路径。

这个实现起来应该不难，A*的消耗也不太大。

#18

如果不是为了研究算法而是解决实际项目问题的话,完全可以把所有枢纽和收费站的信息存入数据库,直接查询得到结果.

#19

at4zhx真是高手啊！！！！！！

#20

#1