Question

The time complexity to find shortest distances by using Dijkstra’s algorithm is __________

(a) O(E^2)

(b) O(V+1-E)

(c) O(V+E)

(d) O(E+VlogV)

I have been asked this question in final exam.

I'd like to ask this question from Trees topic in portion Trees of Discrete Mathematics

Answer 1

Correct option is (d) O(E+VlogV)

For explanation: Time complexity of finding shortest distance can be O(E + VLogV) using Fibonacci Heap. The reason is that Fibonacci Heap takes O(1) time for decrease-key operation while Binary Heap takes O(logn) time.