0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You could calculate the distance between each pair of gas stations + a and b and solve the problem on the new graph (containing only the gas stations and a and b). Remove edges longer than C and set the remaining edges to 1. $\endgroup$ – Albert Hendriks Jul 16 '19 at 8:40
  • $\begingroup$ @qksr55789 Have you ever read Dijkstra's algorithm? That is a classic example of dynamic programming on graphs. $\endgroup$ – John L. Jul 17 '19 at 10:15
  • 1
    $\begingroup$ @Apass.Jack I wouldn't describe Dijkstra as dynamic programming. It's a greedy algorithm. $\endgroup$ – David Richerby Jul 17 '19 at 14:47
  • $\begingroup$ @DavidRicherby I wanted to provide an easily-accessible example for OP to understand how to do dynamic programming on graphs. That is, what might be the entries of DP "table" for graphs and how one can fill more entries from the existing entries. Yes, Dijkstra's algorithm is a greedy algorithm. It could be dynamic programming, where the overlapping subproblems are the shortest paths from the sources to other nodes. There is some controversy on whether Dijkstra' algorithm is dynamic programming. The subtle point is how we find the solution of a larger problem from those of smaller subproblems. $\endgroup$ – John L. Jul 17 '19 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.