求最短路

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

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/245763

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX