3. (16 pts.) DFS variations You are given a set of cities, along with the pattern of highways between them, in the form of an undirected graph G=(V.E). Each stretch of highway e E connects two of the cities, and you know its length in miles, le. You want to get from city s to city. There's one problem: your car can only hold enough gas to cover L miles. There are gas stations in each city, but not between cities. Therefore, you can only take a route if every one of its edges has length ( SL (Note: Only use the algorithms that have been covered in class so far to solve the below problems.) (a) Given the limitation on your car's fuel tank capacity, show how to determine in linear time (IV+ E) whether there is a feasible route from stor. State your algorithm clearly, prove that it is correct and analyze its running time (b) You are now planning to buy a new car, and you want to know the minimum fuel tank capacity that is needed to travel from s to Give an ((IV+ El)log|VD) algorithm to determine this. State your algorithm clearly, prove that it is correct and analyze its running time. (Hint: Use the algorithm in (a) as a subroutine. Consider all the possible values for the minimum tank capacity. How many are there? What would be the running time of the algorithm that tries them all? Then, try to improve this algorithm.) 3b. You need to give an O( (IVI + IEI ) log E) algorithm, rather than an O( (IVI + IEI ) log V) algorithm