Find shortest path from s to every v with a limit on length

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.

So at first I thought about using dynamic programming but I ended up with complexity of O(|V|^3) which apparently not optimal for this exercise.

We can't use Bellman-Ford (As far as I understand) since there might be negative cycles.

What could be an optimal algorithm for this problem?

Thanks

EDIT

I forgot to mention a crucial information; Path can be not-simple. i.e. we may repeat edges in our path.

Answer 1

You can perform a depth limited search with limit of |V|/10 on your graph. It will help you find the path with the least cost.

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)

Answer 2

According to me Bellman Ford's algorithm SHOULD be applicable here with a slight modification.

After iteration k, the distances to each node u_j(k) would be the shortest distance from source s having exactly k edges.

Initialize u_j(0) = infinity for all u_j, and 0 for s. Then recurrence relation would be,

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

Note that in this case u_j(k) may be greater than u_j(k-1).

The complexity of the above algorithm shall be O(|E|.|V|/10) = O(|E|.|V|).

Also, the negative cycles won't matter in this case because we shall stop after |V|/10 iterations. Whether cost can be further decreased by adding more edges is irrelevant.