📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    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