The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
3.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)$

asked in Algorithms by Veteran (59.7k points) | 3.1k views
+16

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

1 Answer

+42 votes
Best answer
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.
answered by Boss (19.9k points)
edited by
0
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
+3
You are correct. For Dijkstra's algorithm, binomial heap and binary heap should give the same complexity.
+5
O((E+V)*LogV) = O(ELogV)
option D
+6
@pC thats not correct if a graph is disconnected. E can be much smaller than V.
+1
@arjun Sir,  is n't the answer option D ?
+11
Answer is option D, but you can't reduce |V| to |E|.
+1
Ok . I understand
0

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

+1
@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.
+1
@ashwani

so it is O( (E+V) log V )  ??
+1
@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
0
@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
0

@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.

You can read this 

Source: Cormen

0

This might help ...

0
@ashwani

so what i can imply is....binary heaps are a form of min or max heaps...and so they have the same complexity ?
+1
@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
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,301 questions
49,794 answers
164,402 comments
65,857 users