algorithm - 找到从 s 到每个 v 的最短路径，并限制长度

Question

Let G(V,E) a directed graph with weights w:E->R. Let's assume |V| is dividable by 10. Let s in V. Describe an algorithm to find a shortest path from s to every v such that it contains exactly |V|/10 edges.

所以一开始我考虑过使用动态规划，但我最终得到了 O(|V|^3) 的复杂度，这显然不是这个练习的最佳选择。

我们不能使用 Bellman-Ford(据我所知)，因为可能存在负循环。

这个问题的最佳算法是什么？

谢谢

编辑

我忘了提一个关键信息；路径可以不简单。即我们可能会在路径中重复边。

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)