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

Question

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

Djikstra 算法在我看来并不能解决这个问题，因为我们无法选择路径的大小。

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

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

Answer 1

不，我不认为 Dijakstra 会做得很好。您不是在寻找以最短距离到达每个节点，您是在寻找以最短距离到达任何地方(即从您的起点开始 k 跳)。

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