GATE CSE 2005 | Question: 38

Question

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:

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

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

• C. $O\left(|V|\log|V|\right)$

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

Comments

$Remarks:$
The complexity of Dijkstra's algorithm depends on how min-priority queue is implemented.

Number of EXTRACT_MIN operations = V, and number of DECREASE_KEY operations = E

1. Using Binary Heap: 
$$O((V + E)logv), EXTRACT-MIN = O(logv), DECREASE-KEY=O(logv)$$
2. Fibonacci heap:
$$O((Vlogv + E)): EXTRACT-MIN = O(logv), DECREASE-KEY=O(1)$$
3. Binomial Heap:
$$O((V + E)logv), EXTRACT-MIN = O(logv), DECREASE-KEY=O(logv)$$
4. Array:
$$O(V^2 + E): EXTRACT-MIN = O(V), DECREASE-KEY=O(1)$$

---

This information must be noted as short notes.one Shold remember while preparing any exam.

---

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time

Answer 1

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$

Comments

@ashwani

so what i can imply is....binary heaps are a form of min or max heaps...and so they have the same complexity ?

---

@Aish

Yes binary heaps are either min heap or max heap but complexity depends on for what purpose you are using, here Dijsksta take min heap so that extract min can be done in Log v but if we take Max heap here then time complexity to extract min will be O(v) as min element can be any leaf of the tree

---

https://en.m.wikipedia.org/wiki/Dijkstra's_algorithm#Running_time