16,144 views
54 votes
54 votes

Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

  1. $O\left(|V|^2\right)$

  2. $O\left(|E|+|V|\log |V|\right)$

  3. $O\left(|V|\log|V|\right)$

  4. $O\left(\left(|E|+|V|\right)\log|V|\right)$

1 Answer

Best answer
74 votes
74 votes
Option $(D)$ :  Binary heap. $|E|$ decrease key operations and each taking $O\left(\log|V|\right)$ time $+$ $|V|$ extract-min operations each taking $O\left(\log|V|\right)$.

Option $(B)$ :  Fibonacci heap. $|E|$ decrease key operations and each taking $O(1)$ time $+$ $|V|$ extract-min operations each taking $O\left(\log|V|\right)$.

Option $(A)$ :  Array. Finding min-vertex in each iteration takes $O(V)$ and this needs to be done $|V|$ times.

Binomial Heap is same as Binary heap here, as the critical operations are decrease key and extract-min.

Correct Answer: $D$
edited by
Answer:

Related questions