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