这是一个创建于 3649 天前的主题，其中的信息可能已经有所发展或是发生改变。
我有一个矩阵，里面储存着两个节点之间距离的长度，假设不可达，如何求两点之间的最短路径？
 | 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