Q5:

Sculder and Mully have been trying to prove the existence of alien life for over a while now. They finally discover that the evidence for extra-terrestrial life is hidden away in one of the government lockers. Unfortunately, Mully is down with the flu: so, it is all upto Sculder, who is now in Los Angeles. Sculder will therefore drive to one of the lockers from Los Angeles, pick up the evidence there, and then bring the evidence to Mully who is in New York. Every locker contains the same evidence, and it suffices to visit one of them.

Sculder obtains the US road network from Giggle Incorporation, which is built as a directed graph and each edge has the travel time from the source vertex of that edge to the destination vertex. Naturally, cities and lockers are vertices on this graph and the roads are the edges.

Design an algorithm to determine which locker Sculder should visit to pick up the evidence and then reach New York as early as possible. State the complexity of your algorithm; assume that there are V cities, roads, and k lockers. Assume that picking up the evidence is instantaneous; time is only needed on the roads.