After you have successfully completed questions. l your implementation of the mi
ID: 3725505 • Letter: A
Question
After you have successfully completed questions. l your implementation of the min-heap operations, answer the following 1. This question will guide you through analyzing the runti of Dijkstra's Algorithm as implemented in this Lab using a min-heap priority queue. For convenience, you may use V rather than the more properVto represent the number of vertices in a graph and similarly for E (a) Consider the pseudocode for the main loop of Dijkstra's Algorithm given on Slide 195 of Lecture 6 (or equivalently, on p. 658 of the textbook) . For a given vertex u that 's just been extracted from the priority queue, which edges are considered for relaxation by this pseudocode? For each edge e = (u, v) in the graph while loop? . How many times does the body of the inner "for loop statement get executed over the course of the entire algorithm, not just in one iteration of the outer . How long does each iteration of the inner "for loop take asymptotically (use O) notation)? (Hint: this is dependent on the fact that we're using a min-heap implementation of a priority queue . How long (asymptotically) does extracting the minimum element u from the heap take in the first line of the outer "while" loop? With this in mind, what's the best asymptotic upper bound you can give on the runtime of Dijkstra's Algorithm as given in the pseudocode on Slide 195 and p. 658 of the text? (Hint: rather than accounting for the entire runtime by multiplying loop counts, split the runtime up into two components: m taken processing vertices with the extractMin cal, and time taken examining neighbor edges for possible relaxations) (b) Now consider replacing the "for loop statement on Slide 195 with the statement For each edge e in the graph instead. How many times would the "or loop body be executed for each iteration of the outer "uhile" loop? How many times over the course of the entire algorithm? . With this in mind, what would the asymptotic runtime of Dijkstra's Algorithm be with the modified "for" loop statement? (c) Be sure your code mplementation uses the version of te or loop given on Slide 195 rather code to take a substantial amount of time to execute. Copy here as the answer to this question the line of Java code you're using as your than the modified version, as the latter will cause your loop conditionExplanation / Answer
a.)
1. All those edges , which start from node u and connect a node v such that the distance of node v from source node is greater than the distance of node u + edge weight , will be processed in this case.
2. This statement will get executed for 2*|E| number of times in the entire program because each edge will get processed 2 times ,first time while processing node which is one end of the edge and second time while processing the node which is other end of the edge.
3. Each iteration of inner for loop will take O(1) time because this will just check whether relaxation will be applied on edge taken in current iteration of inner for loop or not.
4. This will take O( log( |V| ) ) time because extracting a node from min heap having maximum |V| elements will take O( log( |V| ) ) time.
5. Runtime will have |V| extraction from min-heap and each extration will take O( log(|V| ) ) time.So overall |V| extractions will take O( |V|*log( |V| ) ) time.
And the inner for loop will loop through each edge of the graph twice in the entire program which will take O( |E| ) time.
So overall complexity is O( |E| + |V|*log( |V| ) )
b.)
1. Here in each iteration of the "while" loop , "for" loop will executed |E| times.
In total the outer while loop will execute for |V| times .So "for" loop body will be executed |V| * |E| times over the course of the entire algorithm.
2. Runtime will have |V| extraction from min-heap and each extration will take O( log(|V| ) ) time.So overall |V| extractions will take O( |V|*log( |V| ) ) time.
And the inner "for" loop will loop through each edge of the graph in every iteration of "while" loop in the entire program which will take O( |E|*|V| ) time.
So overall complexity is O( |E|*|V| + |V|*log( |V| ) )
c.)
//Here u.list is the list containing all edges that is adjacent to node u.
// edge is class having start node as u, end node as v and weight as w
// dis is an array containing the distance of each node from the source node
for (int i=0;i<u.list.size();i++){
edge e = u.list.get(i);
if (dis[e.v] > dis[e.u]+e.w )
dis[e.v] = dis[e.u] + e.w;
}