Answer Happy

(e) (1.5 points) The pseudo-code is an implementation of the Dijkstra's algorithm. Suppose somebody invented a more sophisticated heap structure where each DECREASE-KEY ope- ration can be done in O(1) time and each EXTRACT-Min operation can be done in O(log n) time, where n is the number of elements in the heap. What is the running time of the algorithm using such a heap? Express the running time in terms of the number of vertices (V) and the number of edges (El). - R=0 d[r] + 0, d[v] + for v ER - {r}. Qk MAKEHEAP({(x, d[x]}xEV) // Put every vertex into the heap. O(V) time. while R+V do 3+ Q.EXTRACT-MIN() // set x to be the vertex with the smallest key R+ RU{x} for y E N(X) - R do if d[y] > d[x] + w(x, y) then d[y] + d[x] + w(x, y) Q.DECREASE-KEY(y,d[y]) // Decrease the key associated with y to d[y] end if end for end while Figure 1: An implementation of Dijkstra's Algorithm R=0 d[s] + 0, d + - for v eR- {s}. o while R+V do ut arg maxreV-R d[x] R + RU{2} for v E N(u) – R do if d <min(d, w(u, v)) then d[v] + min(d, w(u, v) end if end for end while Figure 2: An implementation of Dijkstra's Algorithm