如何从加权图中的顶点找到长度为 k 的最短路径？

Question

有没有一种算法可以在完全加权图中从顶点找到长度k的最短路径？

Djikstra算法在我看来对这道题不适用，因为我们不能选择路径的大小

有算法解决这个问题吗？ Djikstra 算法的变体可以解决这个问题吗？

例如，对于下图 (Graph example)。 当k = 3时，对于顶点A，我们将它们作为A-E-D-C的路径，权重为324。这是权重最小的路径。

Answer 1

如果图表确实像您在问题中提到的那样完整那么这就是子集和问题的一个实例

https://en.wikipedia.org/wiki/Subset_sum_problem

因为 完整 图可以让你随时从任何节点跳到任何节点，所以图的结构并不重要，重要的是权重。问题是 NP-complete 虽然没有有效的方法来做到这一点

如果图表不完整，则需要 Bergi 的回答。昂贵的 BFS 是你唯一的选择

Answer 2

不，我不认为 Dijakstra 会做得很好。您不是在寻找以最短距离到达每个节点，而是在寻找以最小距离到达 anywhere（即从您的起点 k 跃点）。

你可以改用广度优先或深度优先的图遍历，在k为界的搜索树中找到最小距离即可。您可以使用 branch and bound 来优化树搜索。