A question from an exam:
Input:
A map of a country with distances (in km) on roads. some cities have gas stations.
The map is given in the form of directed graph G=(V,E), gas stations are a sub group D of V.
A person wants to get from city a to city b. he starts with a full gas tank which lasts C km.
Output:
A path from a to b with minimum number of stops for refueling (fueling the car when the tank is not empty is possible)
Sounds to me like a dynamic programming problem, but don't really know how to the dynamic programming on graphs.