Problem 4. Highway Driving (12 points) You are given a set of cities, along with
ID: 3740153 • Letter: P
Question
Problem 4. Highway Driving (12 points) 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 t. There is 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 l. s I (a) (6 points) Given the limitation on your cars fuel tank capacity, show how to determine in linear time whether there is a feasible route from s to t. (b) (6 points) 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 t. Give an O(V E)) log E) time algorithm to determine this.Explanation / Answer
a) Feasible_root(G,L)
Sourse s?makeNode(G)
Destination d? makeNode(G)
Put s in in min_pqueue(s, cost)
do while(min_pqueue(s) is not empty)
s?extrct_min_ pqueue(s)
if s is d
return 1 //d (goal) is reachable
processed[i]?s
for each child l of s if (s is not in processed and distance le<=L)
if l is in min_pqueue with minimum cost update it
else put l in min_pqueue(l) with cost
For adjacency list representation it will take time complexity O(ElogV). If path is already given then it will take linear time because there is need to check only if cost of any edge is greater than L is a cause not reachability of destination.
b)Fuel_Capacity(G)
Sourse s?makeNode(G)
Destination d? makeNode(G)
maximumdistance?0
fuelcapacity?0
Put s in in min_pqueue(s, cost)
do while(min_pqueue(s) is not empty)
s?extrct_min_ pqueue(s)
if(maximumdistance<ls)
maximumdistance?ls
fuelcapacity?fuel f require to cover maximumdistance
if (s is d)
return fuelcapacity
processed[i]?s
for each child l of s if (s is not in processed )
if l is in min_pqueue with minimum cost update it
else put l in min_pqueue(l) with cost
For adjacency list representation it will take time complexity O(ElogV).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.