In this problem, we want to determine how to drive a car from point s to...

 

Transcribed Image Text:

In this problem, we want to determine how to drive a car from point s to point t without running out of gas. Our car has a gas tank that is initially filled up to its capacity c. We may have to stop to refuel along the way: we can never allow the amount of gas in the tank to become negative, and we can never fill our tank beyond its capacity. Let us model this problem using a directed graph G = (V, E) with non-negative edge weights wt: E Ro, along with nodes s, t V. For an edge (u, v) E E, wt(u, v) represents the amount of gas required to drive from u to v. Also, a subset FCV represents those points where we may stop to refuel (assume each node v is marked with a bit f(v) indicating whether there is a gas station located at v). Give an efficient algorithm to solve this problem. Your algorithm should determine if there is a viable path from s to t, and if so, output a path that uses the minimum amount of gas. The running time of your algorithm should be O(|F|(|V| + |E|)log|V). Hint: use Dijkstra's shortest path algorithm as a subroutine. You will have to call this subroutine many times. In this problem, we want to determine how to drive a car from point s to point t without running out of gas. Our car has a gas tank that is initially filled up to its capacity c. We may have to stop to refuel along the way: we can never allow the amount of gas in the tank to become negative, and we can never fill our tank beyond its capacity. Let us model this problem using a directed graph G = (V, E) with non-negative edge weights wt: E Ro, along with nodes s, t V. For an edge (u, v) E E, wt(u, v) represents the amount of gas required to drive from u to v. Also, a subset FCV represents those points where we may stop to refuel (assume each node v is marked with a bit f(v) indicating whether there is a gas station located at v). Give an efficient algorithm to solve this problem. Your algorithm should determine if there is a viable path from s to t, and if so, output a path that uses the minimum amount of gas. The running time of your algorithm should be O(|F|(|V| + |E|)log|V). Hint: use Dijkstra's shortest path algorithm as a subroutine. You will have to call this subroutine many times.