这是一个创建于 3242 天前的主题，其中的信息可能已经有所发展或是发生改变。
我有一个矩阵，里面储存着两个节点之间距离的长度，假设不可达，如何求两点之间的最短路径？
 |
1
algas 2015-12-24 10:45:03 +08:00
假设不可达，是说没有办法从一个节点到另一个节点吗?
|
 |
2
zrp1994 2015-12-24 11:03:23 +08:00
分支限界法树搜索求最短旅行商？
|
 |
3
lijun20020229 2015-12-24 11:14:41 +08:00
旅行商是遍历并回到原点，最短路是寻找两点之间的最短路径。
没看出这个有什么特殊的地方，用常规算法不行么？ |
 |
4
wendellup 2015-12-24 11:28:28 +08:00
不可达是啥意思
|
 |
5
syhsyh9696 OP 不可达是不能直接到达
|
|
6
zrp1994 2015-12-24 12:36:25 +08:00
@syhsyh9696 不能到达的节点之间代价设为正无穷，用树搜索很容易就求出来了
|
 |
7
TheCure 2015-12-24 12:42:32 +08:00
这个感觉很常规啊,dijkstra 算法不行吗
长度为负数可以用 floyd |
|
8
algas 2015-12-24 13:24:13 +08:00
根据矩阵，选择距离当前节点为 1 的节点{j}，遍历所有{j}选择到目标节点距离最短的节点作为路径上的下一个节点，依次迭代到目标节点。
|
 |
9
h4x3rotab 2015-12-24 13:30:52 +08:00 via iPhone
那必须是 Dijkstra 和 Floyd 啊，搜索慢死了
|
 |
10
juxingzhutou 2015-12-24 13:40:56 +08:00
这不就是算法导论里面的单源最短路和两点最短路两章吗，去找找这两章的内容就是了，相当完整，基本涵盖了可能的场景。
|
|
11
syhsyh9696 OP 谢谢大家我去翻书
|
Select Language