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

Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.

Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:

1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there
2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)

In this way, you should be able to remove the paths that are going to violate the constraint.