Question

In this question, we will think about how to answer shortest path problems where we have more than just a single source and destination. Answer each of the following in English (not code or pseudocode). Each subpart requires at most a few sentences to answer. Answers significantly longer than required will not receive full credit You are in charge of routing ambulances to emergency calls. You have k ambulances in your fleet that are parked at different locations, and you need to dispatch them to an emergency to help as soon as possible. You have a map of Seattle represented as the adjacency list for a weighted, directed graph G with IV vertices and |E edges, where edge weights are positive numbers representing how long it takes to travel from the source to the destination. (The number of ambulances, k, is significantly less than the number of vertices |V|.) You also have a list of vertices representing the locations of each of your ambulances and the vertex representing where the new emergency is located. Figure 1 shows an example graph 2 2 2 Figure 1: An example graph where k 3 (the highlighted vertices). The emergency is L, and 1, 2, 3 are ambulances F, R, Q are other intermediate locations. The shortest path from 1, 2, and 3 to L are 1-L, 2-Q-L, and 3-2-Q-L respectivel;y (i) Describe how you would use Dijkstra's algorithm to output each of the shortest paths from each ambu- lance to the emergency vertex. (You should output the full route, not just how long it takes.) (ii) What is the runtime for this process? Provide a simplified, tight big-O for the runtime in terms of k, IV, and/or |E|. Use the final version of Dijkstra's algorithm pseudocode from the lecture slides (Lecture 22) to form your answer (iii) How much extra space does this process require? Provide a simplified, tight big-O for the memory usage in terms of k, Vl, and/or |El. Hint: consider the space required for the table of information built in Dijkstra's algorithm (tight-o (IV)) and the space required for the output

Answer 1

a)

Instead of applying dijsktra's algorithm on every ambulance available and finding the shortest , apply dijkstra's algorithm on Emergency Location L as source vertex . As dijktra's algorithm computes shortest path from source vertex to all other vertex find which ambulance is nearest and notify that particular ambulance.

b)

Let us suppose we are using adjacency matrix for graph representation

Total runtime or complexity of this process would be : O(V^2)

c)

Extra space would be required be required is for adjacency matrix and for the final output distances to k ambulances

So total space complexity : O(V^2 + k )