首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >两个节点之间最便宜和最短的路径

问两个节点之间最便宜和最短的路径
EN

Stack Overflow用户
提问于 2016-12-03 21:20:19
回答 1查看 1.5K关注 0票数 2

我需要在带圈的加权图中找到两个节点之间最便宜和最短的路径。我正在Prolog中实现这一点。

由于我必须找到最便宜的(最便宜的)和最短的(最短的)路径,所以我认为应该使用深度搜索来计算现有的所有可能的路径--首先使用回溯搜索,因为它的内存消耗较低,而且速度相对较快(我使用一个辅助列表来跟踪访问的节点以处理循环问题),然后从收集到的路径列表中选择最便宜和最短的路径。

我排除了使用启发式算法(例如A*)的可能性,因为这些算法虽然速度更快,但依赖于估计函数,而且在某些具体情况下,估计可能是错误的,它们可能给出错误的答案。我不想要一个好的解决方案,我想要最好的解决方案。

因此,我的问题是:我给出的解决这个问题的方法是否更有意义,更确切地说,是为了确保我在有循环的两个节点之间的图问题中得到了最多或最便宜的路径,是否有意义计算所有现有的解决方案,然后通过将其与其他方案进行比较来选择正确的方案,还是我处理这个问题的方法是错误的?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-12-03 21:45:47

这里没有必要使用自定义算法。您可以使用一个标准的最短路径查找算法(Dijkstra的,如果所有的权重是非负的,福特-Bellman或弗洛伊德的,否则)。边的权重应该分别是第一个问题和第二个问题的代价和距离。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/40952628

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档