Consider the version of Dijkstras algorithm shown above written by someone with access to a priority queue data structure that supports only the Insert and ExtractMin operations. this version simply inserts the pair (x, d0 (x)) into Q. The danger with this algorithm is that a node x may occur several times in Q with different values of d 0 (x). Answer the following questions.

1) When the algorithm inserts a pair (x, d1) into Q, suppose the pair (x, d2) is already in Q. What is the relationship between d1 and d2?

2) Using this relationship, how will you fix this algorithm? You just have to describe your correction in words, e.g., by saying I will add the following command after Step X: . . . You do not have to prove the correctness of your algorithm.

3) What is the running time of this modified algorithm? Just state the bound in terms of the number of nodes n and the number of edges m in G

4: 1: INSERT(Q,3,0). 2: while S + V do 3: (v, d'(v)) = EXTRACTMIN(Q) Add v to S and set d(u) = d'(U) 5: for every node x e V - S such that (0, 2) is an edge in G do if d(v) +1(0,x)