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

asked in Algorithms by Veteran (69k points) | 2.1k views

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:

1 Answer

+37 votes
Best answer
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.
answered by Veteran (19.8k points)
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.
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) ?


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.

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

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

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


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

This might help ...


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

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

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

33,687 questions
40,230 answers
38,793 users