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 (b) Now, by modifying the graph representation, we're going to discover a more efficient algorithm for this prob- lem. Suppose we made a copy of the graph G where every edge is reversed (also represented using an adjacency list). That is, every edge from u to v in the original graph has a corresponding edge from to u with the same weight in the new graph (where and u' represent the copies of v and u respectively). (i) What is the runtime of making this reversed copy of the graph? Provide a simplified, tight big-O for the runtime in terms of k, Vl, and/or |El, assuming that our adjacency list uses hash dictionaries where each put takes constant time. (ii) How much extra space does it take to store the reversed copy of the graph? Provide a sinnplified, tight big-O for the memory usage in terms of k, Vl, and/or |E|. (ii) Describe how you would use Dijkstra's algorithm on the reversed graph to output the shortest paths from each ambulance to the emergency vertex. (Again, you should output the full route, not just how long it takes.) (iv) What is the runtime for this entire process (including creating the reversed graph and running Dijkstra's algorithm)? Provide a simplified, tight big-O for the runtime in terms of k, VI, and/or |E|. As mentioned before, use the final version of Dijkstra's algorithm pseudocode from the lecture slides (Lecture 22) to form your answer. (v) How much extra space does this entire process require (including creating the reversed graph and running Dijkstra's algorithm)? Provide a simplified, tight big-O for the memory usage in terms of k, V, and/or E. (Reminder: the space complexity of Dijkstra's algorithm is tight-o (IVI)) (vi) How is this algorithm better than the one in part (a)? How is it worse?

Answer 1

b)

i)

To make new copy of reverse graph we require total edges knowledge of original graph

because we are using hash dictionary insertion time is constant

So total time required would O(V + E).

ii)

For storing reverse we need to store details of all vertices and edges through adjacency list

Complexity : O(V+E).

iii)

Instead of appying shortest path algorithm on all edges we just apply it once on Emergency location and we try to maintain parent vertex for path retrieval. So that we can obtain full path route and also shortest distance

iv)

For creating reverse graph O( V + E )

As we are using adjacency list and if we try to use priority queue , Our total runtime would be O ( V + ElogV ) as insertion and searching in priority queue is logV

Total Complexity would be O ( V + E + ElogV )