我有一个矩阵，里面储存着两个节点之间距离的长度，假设不可达，如何求两点之间的最短路径？
This topic created in 3805 days ago, the information mentioned may be changed or developed.
 |
1
algas Dec 24, 2015
假设不可达，是说没有办法从一个节点到另一个节点吗?
|
 |
2
zrp1994 Dec 24, 2015
分支限界法树搜索求最短旅行商？
|
 |
3
lijun20020229 Dec 24, 2015
旅行商是遍历并回到原点，最短路是寻找两点之间的最短路径。
没看出这个有什么特殊的地方，用常规算法不行么？ |
 |
4
wendellup Dec 24, 2015
不可达是啥意思
|
 |
5
syhsyh9696 OP 不可达是不能直接到达
|
|
6
zrp1994 Dec 24, 2015
@syhsyh9696 不能到达的节点之间代价设为正无穷，用树搜索很容易就求出来了
|
 |
7
TheCure Dec 24, 2015
这个感觉很常规啊,dijkstra 算法不行吗
长度为负数可以用 floyd |
|
8
algas Dec 24, 2015
根据矩阵，选择距离当前节点为 1 的节点{j}，遍历所有{j}选择到目标节点距离最短的节点作为路径上的下一个节点，依次迭代到目标节点。
|
 |
9
h4x3rotab Dec 24, 2015 via iPhone
那必须是 Dijkstra 和 Floyd 啊，搜索慢死了
|
 |
10
juxingzhutou Dec 24, 2015
这不就是算法导论里面的单源最短路和两点最短路两章吗，去找找这两章的内容就是了，相当完整，基本涵盖了可能的场景。
|
|
11
syhsyh9696 OP 谢谢大家我去翻书
|
Select Language