SSSP Algorithm: Minimum distance but under a certain number of "hops"

Question

Given a directed, weighted graph (with no negative edges), what is the shortest distance from one node to other that also fulfills the condition that the number of "hops" from one node/vertices to another must be less than a certain value k. (Where k is definitely less than the number of nodes).

One "hop" is defined to be moving from one node to another, and the "hop" value starts at 1 from the source node.

The problem is not as simple as to simply run Dijkstra's algorithm, since this algorithm only gives you the shortest distance without consideration of the number of "hops".

Consideration 1: The shortest path from source to end node may exceed the maximum number of "hops" allowed.

Consideration 2: Augmenting the Dijkstra's algorithm to minimize the number of "hops" will give you a possible answer but it may not be the shortest.

Note that the priority here is still to minimize the shortest distance, just that there is a new condition of the number of "hops" needing to be less than a certain value.

Answer 1

There is a solution that modifies the Bellman-Ford algorithm for your specific case. On the classical Bellman-Ford ( https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm ) you should do N-iterations.

The idea of the solution is the following,

Set distance[root] = 0, and distance[x] = infinity for every other node.

Now, we will loop through all edges once and try to improve our answer.

For Edge in Edges:
    distance[Edge.dest] = min( distance[Edge.dest], distance[Edge.src] + Edge.cost)

Applying this step once will give us the shortest path from origin that uses at most one edge. Now the idea is to repeat this step exactly K times. This will give us exactly the shortest path from the origin to every other node using at most K edges.

Complexity: O( K * |edges| )