You are given a set of cities along with the pattern of high

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 kilometers l(e). You want to get from city s V to city t V . There is one problem: your car can only hold enough petrol to cover L kilometers. There are petrol stations in each city, but not between cities. Therefore, you can only take a route if every one of its edges has length no greater than L.

1) 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.

2) 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.

Solution

For first part of the question do the breadth first search(bfs) starting from node \'s\'. If you find an edge during traversal whose length is more than L then don\'t process that edge. During the bfs if the current processing node is \'t\' then you know that there is a route from s to \'t\' whose maximum edge length is less than or equal to L. For example Suppose there are 5 city connecting the highway. Supoose maximum distance my car can cover from one city to another is 7 kms. Suppose these are the city connected directly by the highway having some distance -

1 -> 2 , 3kms

1-> 4, 4kms

1 -> 8, 8kms

2 -> 3, 2kms

3 -> 5, 2kms

Suppose your starting city is 1 and destination is 5. So only edge which will not process is 1-5 (directly connected) due to its length greater than 7. And there is a path 1-2-3-5 which makes 1 and 5 connected and we have our solution.

You can also use dfs in this case if you want.

For second part you need to build minimum spanning tree and after that do the dfs/bfs from source node \'s\' until you find destination node \'t\'. Now how do I know if this is correct method. First of all spanning tree will get you all the connected vertices of source node s with minimum total weight. As the path will be unique here so you will get the minimum distance edge after doing bfs/dfs. To buid the spanning tree you can use prim\'s algorithm.

There is another solution of little different complexity. Binary search the maximum length of longest road connecting city. If the choosen length find the path(again using bfs/dfs like in first question) from s to t then we know that maxium distance cover by my car from source to destination will be that length. We modify the length according to the result. I will not go into detail but if you want to know more you can ask in comment.