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:

- Shortest path
**0->2**with**n = 2**is**18** - Shortest path
**0->3**with**n = 3**is**22** - 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?

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

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.

answered Mar 16 '23 21:03
#### Matt Timmermans

### Recent Activity

- Apple Pay - authorize.net returns error 153 only when live, sandbox works
- How to continue cursor loop even error occured in the loop
- python find all neighbours of a given node in a list of lists
- Fatal error: Call to a member function setColumn() on a non-object in Magento
- Count how many of each value from a field with MySQL and PHP
- Python 32-bit development on 64-bit Windows [closed]

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