You are given a set of cities, along with the pattern of highways between them, in the
Question:
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’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 le ≤ L.
(a) Given the limitation on your car’s fuel tank capacity, show how to determine in linear time whether there is a feasible route from s to t.
(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 t. Give an O((| V| + |E |) log | V|) algorithm to determine this.
Introduction to Data Mining
ISBN: 978-0321321367
1st edition
Authors: Pang-Ning Tan, Michael Steinbach, Vipin Kumar