Dijikstras Algorithm problem
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 condition