GATE Overflow Test Series | Algorithms | Test 2 | Question: 24

Question

Which of the following is/are correct with respect to Dijkstra's algorithm to find Single Source Shortest Path in a weighted directed graph $G$? (Mark all the appropriate choices)

• A. Dijkstra's algorithm runs in $O(|E| \lg |V|)$ if priority queue is implemented with a binary min-heap
• B. For dense graphs $(|E| = \Omega(|V|^2))$ Dijkstra's algorithm performs better if priority queue is implemented with an array
• C. Dijkstra's algorithm has a worst case time complexity of $O(|V|^2)$
• D. Dijkstra's algorithm has a worst case time complexity of $O(|V|\lg |V| + |E|)$ when implemented with a Fibonacci heap

Comments

@gatecse Answer should be A, B, D. Dijkstra’s algorithm has a worst case time complexity when there is a dense graph and priority queue is implemented with priority heap. It comes out to be $O(V^2 logV)$. Plz correct me if I’m wrong. 

Why should the answer be C as well ? - because when nothing is given about implementation of algorithm and question asks about worst case then we take worst case time complexity of optimal algorithm. This answers my question. Thanks for reading 🙏

---

@Quantum City So when we’re using the Optimal algorithm shouldn’t we be using the optimal data structure as well which is Fibonacci Heap which will give us the Worst Case Time Complexity as $O(V\log(V) + E)$

Answer 1

All the given statements are correct.

When nothing is mentioned about the data structure to be used we can assume the best possible data structure.

Comments

Option c is quite unclear to me. Please anyone explain how is it correct. I think not much of the information has been given to derive conclusion.

---

@Arjun @Sachin Mittal 1 @gatecse sir,

For option C if it is implemented using Fibonacci heap and adj matrix, then the time complexity will be (O(V^2)).

But if it is implemented using binary min-heap + adj matrix, then the time complexity will be  O((V^2)lgV).  

So, sir it is not told which implementation to follow, then how we can say this is true.

---

@Arjun @Sachin_Mittal_1 @gatecse sir,

In option B, should we interpret “if priority queue is implemented with an array” as array being a sorted array? I’m asking because, i’m not sure if a normal array can be a priority queue.