# Shortest path with a maximum number of vertices

### Tags:

#### graph-algorithm

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?

678
asked Mar 14 '23 08:03

#### novalain

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))`

134
answered Mar 16 '23 22:03

#### throwit

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.

24
answered Mar 16 '23 21:03

## Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!