Question 2: Graph Algorithms [20 Points] Consider the following code for implementing Dijkstra's Algorithm: Dijkstra (G,

[answerhappygod]

Question 2 Graph Algorithms 20 Points Consider The Following Code For Implementing Dijkstra S Algorithm Dijkstra G 1 (91.73 KiB) Viewed 43 times

Question 2: Graph Algorithms [20 Points] Consider the following code for implementing Dijkstra's Algorithm: Dijkstra (G, S) || G is a graph, s is the source for each vertex u in G 2 u.d = 0 UT = NULL s.d = 0 Create a priority queue Q and insert all vertices in it while Q is not empty u = Q.Extraction for each vertex v in u's adjacency list (in alphabetical order) if X1 10 v.d = X2 X3.IT = X4 (a) Replace X1, X2, X3 and X4 with the right expressions. (4 points) (b) If Dijkstra's algorithm is applied to the graph below with the source being A, how many times will each of the following lines in the algorithm be executed? Give the exact numbers (no asymptotic notation) (6 points) 3 4 5 6 7 8 9 NO 11 B A fi N 5 D Line 7 Line 9: Line 10

(c) Does Dijkstra's algorithm always compute the optimal solution when the graph has negative- weight edges? If yes, give a logical argument proving this. If no, give a counter example and explain it. (2 points) (d) Suppose that after applying Dijkstra's algorithm to a given directed graph with positive edge weights, a new vertex was added to the graph with some outgoing and incoming edges that connect it to some or all of the existing vertices in the graph. Give an efficient algorithm that computes each of the following and analyze the asymptotic complexity of each algorithm. Credit will depend on the efficiency of your algorithm. To get credit, your algorithm must be more efficient than simply rerunning Dijkstra's algorithm on the new graph. Assume that each vertex in the graph, including the new vertex, has two adjacency lists: one containing the neighbors connected by outgoing edges (succList) and one containing the neighbors connected by incoming edges (predList). a. An algorithm that computes the minimum distance from the source to the new vertex Write the actual pseudo-code. (4 points) b. An algorithm that finds the largest possible set of vertices whose minimum distances from the source are guaranteed not to change after the addition of the new vertex, that is, the set of vertices whose minimum distances do not need to be updated (or recomputed). In this part, you only need to give a high-level description, you don't have to write pseudo- code. You can use any standard algorithms studied in class by referring to them without having to write their pseudo-code. (4 points)