Problem 4. Highway Driving (12 points) You are given a set of cities, along with

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, l.. 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((VI +E)) log |E) time algorithm to determine this

Explanation / Answer

(a) The trivial solution for the given problem is. first remove all the edges which are greater than L.

After that apply the Depth-First-Search between the city s and look whether the city t will be reached.

The running time of the depth-first-search is linear. Thus, the time would be 0 (V + E).

(b) • To solve this problem. find the path between the two cities s and t.

• Such that the edge of the largest weight would be the smallest path. This is the bottleneck path for the two cities. • The bottleneck edge would be the maximum length of an edge on the path of the bottleneck.

• But not always the bottleneck path would be the shortest path.

• The shortest path can be obtained by the Dijkstra's Algorithm.

To obtain the bottleneck path, modify the Dijkstra's Algorithm as follows:-

• In the Dijkstra's Algorithm. there is field called as d for each vertex and it is the key field for the priority queue.

• Replace d with distance.

• a.distance refers to the length of the edge of the bottleneck in the path of the bottleneck from the city s to a.

• The distance now be the key for the priority queue.

• Initialize s.distance = 0 and a.distance = 'eta' all values of a eV{s}.

• Modify the Dijkstra's Algorithm. by replacing the Initialize-Single-Source(G. s) with Initialize-Single-SourceBottleneck(G.$) and Relax(a. b. c) with Relax-Bottleneck(a. b. c)

Initialize-Single-SourceBottleneck(G.$)

for each vertex b e G.V

b.distance = infinity

b. pi = nil

s.distance = 0

Relax-Bottleneck(a. b. c)

if max(a.distance. c(a.b)) < b.distance

b.distance = max(a.distance, c(a, b))

b. pi=a
• The path of the bottleneck follows the property of optimal subroutine.

• For each of the vertex b, if b is the successor of the vertex a in the path of the bottleneck from the city s to b, the bottleneck edge would be either the path between the city s to a or the edge (a, b), whichever is largest would be considered.
• This is implemented in the above Relax-Bottleneck subroutine.

• The complexity would be 0 ((E + V) lgV) = 0(E Ig V)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.