9. Running on empty. 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 R20, along with nodes s'te V. For an edge (u, vje E, wt(u, v) represents the amount of gas required to drive from u to v. Also, a subset F CV 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(IFI(IV+E1) log |V) Hint: use Dijkstra's shortest path algorithm as a subroutine. You wi have to call this subroutine many times 9. Running on empty. 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 R20, along with nodes s'te V. For an edge (u, vje E, wt(u, v) represents the amount of gas required to drive from u to v. Also, a subset F CV 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(IFI(IV+E1) log |V) Hint: use Dijkstra's shortest path algorithm as a subroutine. You wi have to call this subroutine many times