algorithm - 如何找到最小权重的 k 长度路径？

Question

给定 V 个顶点:V1,V2,V3....,V300。对于所有小于 j 的 i，存在从 Vi 到 Vj 的一条边，我们得到了每条这样的边的权重。我们必须找到从 V1 开始的 k 长路径(即恰好访问了 k 个顶点)，并且可以在任何其他顶点结束，使得权重最小。

我已经用 dp 尝试了 Bruteforce，这给了我 O(2^n) 这很慢。

Answer 1

您可以利用您的图是非循环的这一事实来获得时间复杂度为 O(n ^ 3) 的动态规划解决方案。

我们假设 f(v, length) 是以 v 顶点结束并恰好包含 length 的路径的最小权重顶点。最初，对于所有 v，f(v, 1) = 0(因为只有一个顶点的路径的权重为 0)。然后你可以遍历从 1 到 n 的所有顶点来计算 f 值:

for i = 1 ... n
    for j = 1 ... i - 1
        for length = 1 ... k
            f(i, length + 1) = min(f(i, length + 1), f(j, length) + dist(j, i))

对于所有 v，答案是 min(f(v, k))。