Shortest path with a maximum number of vertices

Question

I want to find the shortest path between two vertices with an additional constraint : max n vertices can be visited. The graph is directed, connected, non negative weights and may contain cycles.

Example:

1. Shortest path 0->2 with n = 2 is 18
2. Shortest path 0->3 with n = 3 is 22
3. Shortest path 0->3 with n = 4 is 9

So far I've implemented Djikstras algorithm to get the simple shortest path, and my idea was to keep a counter of the current vertices visited, if it exceeds n it takes one or more steps back and tries with another path.. but as far as I know Djikstras can't be used for backtracking as explained here.

Another idea is somehow to store every path between every node in a table. But I'm not really sure how Djikstra can discover the path 0->2 with weight 18 since it is not really a shortest path...

Does anyone have any ideas how to tackle this problem?

Answer 1

Divided each vertices into n vertices, that is, for vertices u, we create n vertices expressed as (u, 1) ... (u, n), the second number shows the number of steps to this vertices. For each edge from u to v, we create an edge from (u, i) to (v, i+1) where 1<=i<=n-1 in new graph. Now if you want to calculate the shortest path between u and v with n, just do Dijkstra from (u, 1), then your answer is min(result (v, i) | 1<=i<=n)

The total number of vertices can be n*n, so the complexity is about O(n^2*log(n^2))

Answer 2

Let COST_TO(v,n) be the total weight of the minimum path to vertex v with n edges or less.

When n=0, the answer is easy:

for all v, COST_T(v,0) = 0 if v is the source vertex and infinity otherwise

For n>0, COST_TO(v,n) is the minimum of COST_TO(v,n-1) and all COST_TO(w,n-1)+WEIGHT(w,v), where there is an edge from w to v

so, for n = 0 to N, keep track of all the vertices with COST_(v,n) < infinity along with their costs, and calculate the costs for n from the values for n-1.

At the same time you can keep track of the minimum weight path to each v -- every time you update the cost to v with the edge rule, the new path to v is the path to w plus that edge. A reverse-singly-linked list is handy for this.