从 s 到每个 v 找到最短路径，且路径长度受限。

Question

让 G（V，E） 成为一个带权重的有向图，权重为w：E -＆gt; R 。假设 | V | 可以被 10 整除。让 s 在 V 中。描述一种算法，以找到从 s 到每个 v 的最短路径，使其包含恰好 | V |/10 个边。

所以起初我想使用动态编程，但最终复杂度为O（| V | ^ 3），显然不适用于这个问题。

我们不能使用贝尔曼福特（据我所知），因为可能存在负循环。

对于此问题，什么是最优算法？

谢谢

编辑

我忘记提供关键信息; 路径可以不是简单的，也就是说，我们可以在路径上重复边缘。

- Elimination

---

你能解释一下你的 O(|V|^3) 算法吗？ - Saeid

Answer 1

你可以在图上执行深度有限搜索，并将其限制为 |V|/10，这将帮助您找到最小成本路径。

limit = v_size / 10
best[v_size] initialize to MAX_INT

depth_limited(node, length, cost)
    if length == limit
        if cost < best[node]
            best[node] = cost
        return
    for each u connected to node
        depth_limited(u, length+1, cost + w[node][u])

depth_limited(start_node, 0, 0)

- Saeid

---

抱歉，我忘了提到路径可能不简单（即重复边）。 - Elimination

此方案不会限制重复的边缘。 - Saeid

Answer 2

根据我的理解，Bellman Ford算法应该可以在这里进行轻微修改后应用。

迭代k之后，每个节点u_j(k)的距离将是从源s到该节点恰好经过k条边的最短距离。

对于所有的u_j，将u_j(0)初始化为无穷大，将s初始化为0。然后递归关系式为：

u_j(k) = min {u_p(k-1) + w_{pj} | There is an edge from u_p to u_j}

请注意，在这种情况下，u_j(k)可能大于u_j(k-1)。

上述算法的复杂度应为O(|E|.|V|/10) = O(|E|.|V|)。

此外，在这种情况下，负循环不重要，因为我们将在|V|/10次迭代后停止。是否可以通过添加更多边来进一步降低成本并不重要。

- Abhishek Bansal

---

抱歉，但我忘了提到路径可能不简单（即可以重复边）。 - Elimination

我喜欢这个解决方案。它本质上是使用|V|*|V|/10内存的Bellman-Ford算法，对吗？而且我认为复杂度应该是O(E*V)而不是O(V^2)，对吗？ - Saeid

@Elimination 没问题，这个算法允许这种情况。 - Abhishek Bansal

@sudomakeinstall2 是的，时间复杂度应该是 O(EV)。已编辑，谢谢。 - Abhishek Bansal