GATE 2006-IT
April 6, 2025GATE 2002
April 7, 2025GATE 2005
| Question 38 |
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:
| O(|V|2) | |
| O(|E|+|V|log|V|) | |
| O(|V|log|V|) | |
| O((|E|+|V|)log|V|) |
Question 38 Explanation:
O(ElogV) equals to O((|E|+|V|)log|V|)
In worst case graph will be a complete graph i.e total edges = v(v-1)/2 where v is no. of vertices.
E<=v2
Time Complexity of Dijkstra’s algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v2 + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
In worst case graph will be a complete graph i.e total edges = v(v-1)/2 where v is no. of vertices.
E<=v2
Time Complexity of Dijkstra’s algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v2 + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
Correct Answer: D
Question 38 Explanation:
O(ElogV) equals to O((|E|+|V|)log|V|)
In worst case graph will be a complete graph i.e total edges = v(v-1)/2 where v is no. of vertices.
E<=v2
Time Complexity of Dijkstra’s algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v2 + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
In worst case graph will be a complete graph i.e total edges = v(v-1)/2 where v is no. of vertices.
E<=v2
Time Complexity of Dijkstra’s algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v2 + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)