Problem 4-2. You are given a graph G = (V, E) and you want to drive from a location s to another location t without running out of gas while spending as little money as possible. You are given a map of the road system designated by a set of vertices and a set of directed roads (one way) where (u, v) E E means that there is a road from vertex u to vertex v. w(u, v) is the length of the road from u to v, and it uses up w(u, v) gas units. You also know that some vertices R V have gas stations. When you get to a vertex with a gas station, you can either pay c(u) > 0 dollars to fill up your tank, or not get gas. (Note that the cost does not depend on the amount of gas you get, only on the gas station location. So you may as well fill up your tank if you are getting any gas.) Assume that you start with a full tank with k units of gas. Here, we will try to design an algorithm to get from s to t without running out of gas and spending as little money as possible on gas. Note that this is not a normal shortest paths problem since you don't want to find the shortest path from s to t. That is, we want to construct a graph G' =(V', E') 2 such that solving shortest paths in G' solves our problem (finding the cheapest path from s tot in G). (a) Construct this graph G' = (V', E") and the shortest path problem such that the length of this shortest path on G' is equal to the minimum cost of going from s tot in G. Hint: This graph contains a subset of the vertices in G. Think about which subset suffices. Also, the edge weights should use c(u)'s somehow. (b) Analyze the running time of your algorithm based on this reduction. In particular, the algorithm consists of two parts: constructing G' given G and then running shorest paths on G'. Analyze the running time of both these components in terms of |VI, El, and S. The sum of these two quantities is the running time of your algorithm. You may assume that running Dijsktra's algroithm on a graph with n nodes and m edges takes Om +n log n) time. Note: Since G' might have different number of nodes and edges than G, you must compute how many nodes and edges G' might have in terms of |V], E), and S and then state the running time in terms of these quantities. If you state the running time in terms of the number of nodes and edges in G', you will lose points