[Math] Constrained Shortest Path Dijkstra

Question

Here is my problem: I have my graph and I want to find the shortest path constrained in terms of number of vertex passed by.

I have tried to apply Dijkstra with some modifications but obviously for some graphs I obtained a sub-optimal solution. I want to achieve the optimal one.

I am pretty sure this has been done, but I don't know where to find it. I have found solution for having a fix number of vertex passed by (hops) but what I want instead of that is a constrain in the maximum number of hops, not a fixed one.

Thanks

---

EDIT:

My problem is similar to a-Autonomy Shortest Paths:
I want to go by car from S to D. I don't have enough fuel. I can stop at two(k) petrol stations in my way.

So for example given this graph:

S–R1–R2–F–D
\······················/
··Z1———-Z2

Here for example from S to F the shortest and optimal path would be S-R1-R2-F, refuelling at R1 and R2.
This path is also valid for going from S to D, I can refuel at R1 and R2. However, that is a suboptimal path, since for going from S to D refueling at max 2 times I might have a better path refuelling at Z1 and Z2.
As you see my problem is not in terms of hops, is in terms of 'where do I refuel', that as in Dijkstra I base the status of D based on the predecessor F, suboptimal path might not be reached.

I don't know whether I made it to clarify my self or not….but it would be nice if you give me any hint on how to do it.

Thanks

Answer 1

Instead of modifying Dijkstra’s algorithm, you can modify the input graph. Create a “layered” graph with nodes $(i,k)$, where $i$ is an original node and $k$ is the number of hops so far, and edges from $(i,k)$ to $(j,k+1)$, where $(i,j)$ is an original edge.