What is running time of Dijkstra’s algorithm using Binary min- heap method?
A. O(V)
B. O(VlogV)
C. O(E)
D. O(ElogV)
Answer:D
What is running time of Dijkstra’s algorithm using Binary min- heap method?
A. O(V) B. O(VlogV) C. O(E) D. O(ElogV)
Explanation: Time required to build a binary min heap is O(V). Each decrease key operation takes O(logV) and there are still at most E such operations. Hence total running time is O(ElogV).