2.1k views

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)$

$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)$$

D. Binary heap. $|E|$ decrease key operations and each taking $O\left(\log|V|\right)$ time plus $|V|$ extract-min operations each taking $O\left(\log|V|\right)$.

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

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

Binomial Heap- same as Binary heap here as the critical operations are decrease key and extract-min.
edited by
I doubt that the time using binomial heap will be less than using fibonacci heaps as below wiki article tells that fibonacci heaps are more efficient than binomial heaps.

https://en.wikipedia.org/wiki/Fibonacci_heap
You are correct. For Dijkstra's algorithm, binomial heap and binary heap should give the same complexity.
O((E+V)*LogV) = O(ELogV)
option D
@pC thats not correct if a graph is disconnected. E can be much smaller than V.
@arjun Sir,  is n't the answer option D ?
Answer is option D, but you can't reduce |V| to |E|.
Ok . I understand

If it was min heap it will be O (E log V) ?

@Aish

If min heap is asked, time complexity will remain same because extract min can be done in constant time but we have to remove it from heap there might be a chance that min heap property of overall heap affected which in turn need log v time  at max to maintain it.
@ashwani

so it is O( (E+V) log V )  ??
@Aish

Yes there will be no change and time complexity remains T(n)= O((E+V)log V

|V| extract min operations and  |E| relax operations where  each operation taking log V time
@ashwani

incase of min heap E decrease key will take log V because if we decrease the value the property of min heap is disturbed and so we have to rebalance

incase of binary heap there is catually no requirement like that right?

why would it require log V time

@Aish

Binary heap will take log V time for extract min operation and decrease key operation because if I am not wrong when we say a binary heap then it is an almost complete binary tree with heap property which is either it is Max heap or min heap itself.

In case of Dijkstra when we were implementing min priority queue as an array time taken was O(V² + E) so in order to improve this time we used binary min heap as min priority queue.

Source: Cormen

This might help ...

@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