📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!
  • google app store apple app store
    • âś–

      Question

      For Dijkstra’s algorithm on a graph with non-negative

      weights, which data structure yields the best time complexity for dense graphs?
      A Binary heap Correct Answer Incorrect Answer
      B Fibonacci heap Correct Answer Incorrect Answer
      C Simple array (scan for min) Correct Answer Incorrect Answer
      D Balanced BST Correct Answer Incorrect Answer
      E Unordered queue Correct Answer Incorrect Answer

      Solution

      For very dense graphs (E ~ V²), using a simple array to find minimum gives O(V²), which is often comparable or better than heap-based approaches because decrease-key overhead and E log V terms dominate. Fibonacci heap improves sparse graphs but has overheads.

      Practice Next
      More Data Structure Questions
      ask-question