Travelling with resource constraint?

Question

Your friend X has recently purchased a THUNDERBIRD motorcycle. He is very excited and wants to drive it from some town s to another town d in Thar desert (think of Sahara desert if you are more adventurous). He is provided with the complete road map of the desert - the roads, their lengths and junctions (where two or more roads meet). The mobike has a very natural limitation - it can drive for c kilometers with full fuel tank. Since the destination is very far, X must plan his route so that he can refill the fuel tank along the way. Note that the shortest route may not necessarily be the feasible route. You friend is bit confused and scared - what if he gets lost in Thar desert due to improper planning. Your friend is very proud of you. He also knows that you have done a course on algorithms. He approaches you with full faith that you will help him find the shortest feasible route from s to d if it exists. Model the problem in terms of a weighted, undirected graph in which roads are edges, junctions are vertices, and some junctions have fuel stations, and design an efficient algorithm to find shortest feasible route from s to d and inform if no route is feasible. Assume that both s and d are also at junctions and the source s has a fuel station. Your algorithm should take time of the order of O(mn log n) where m is the number of edges and n is the number of vertices. You should not exploit the planarity of the input graph while designing your algorithm. In other words, your algorithm should work for any arbitrary undirected graph with positive edge weights and under the fuel constraint mentioned above. Also note that the shortest feasible route need not be a simple path. For example, consider the following situation : There are five towns : s, a, b, e, d where fuel stations are available at s, b, e only. The connecting roads are : (s, a) of length 200 km, (s, d) of length 300 km, (a, b) of length 40 km, (a, d) of length 150 km, (b, e) of length 200 km, (e, d) of length 200 km; and motor bike can travel 250 km with full fuel tank. For this road network, shortest feasible route from s to d is is s → a → b → a → d, and has length 430 km.

Can anyone give slight hint or idea on how to approach this type of problem?

Answer 1

Shortest path problems with side constraints often can be turned into unconstrained shortest path problems on a derived graph. One possibility is to expand the idea of location from junction to (junction, fuel level), but the requested time bound doesn't allow dependence on the size of the fuel tank. What does work here is to find shortest paths in a graph on junctions with fuel stations (including s) and d, with an edge between each pair of junctions such that the shortest path has length at most the range of the bike. The weight of each edge is the length of this shortest path.