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