Dijkstra's algorithm using a binary min-heap runs in
AO(V²) regardless of E
BO(E log V) using a binary min-heap
CO(V + E), like BFS
DO(E + V log V), using a Fibonacci heap
Answer & Solution
Correct answer: B. O(E log V) using a binary min-heap
Binary heap: V Extract-Min calls at O(log V) plus up to E Decrease-Key calls at O(log V). Total O((V + E) log V) which simplifies to O(E log V) for connected graphs. O(V²) is the naive-array version on dense graphs; O(V + E) is BFS; O(E + V log V) is the Fibonacci-heap version (better, but harder to implement).
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for