如何从加权图中的顶点求出长度k的最短路径？
如何从加权图中的顶点求出长度k的最短路径？
提问于 2019-05-05 17:58:36
在完全加权图中，是否有算法从顶点找到长度k的最短路径？
在我看来，贾克斯特拉算法并不适用于这个问题，因为我们不能选择路径的大小。
它有解决这个问题的算法吗？贾克斯特拉算法的一个变体能做到这一点吗？
例如，对于下面的图(图例)。在k= 3的情况下，对于顶点A，我们会给它们一条像这样的路径，宽度为324。这就是重量最小的路径。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-05-05 18:39:39
如果图确实是完全，就像您在问题中提到的那样，那么这就是子集和问题的一个实例。
由于完全图允许您在任何时候从任何节点跳到任何节点，所以图的结构并不重要，只是权重。问题是NP-完全，所以没有有效的方法来做到这一点。
如果图不是完整的，那么Bergi的答案是必要的。昂贵的BFS是您唯一的选择。
Stack Overflow用户
发布于 2019-05-05 18:42:23
不，我不认为Dijakstra会做得很好。您并不是在寻找到达每个节点的最短距离，而是希望以最小的距离到达任何地方(即k跳距您的原点)。
您可以使用宽度优先或深度优先图遍历来代替，只需在搜索树中找到以k为界的最小距离。您可以使用枝界优化树搜索。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55994828
复制相关文章
相似问题
腾讯云开发者
