UGC NET CSE | June 2007 | Part 2 | Question: 21

Question

The time required to find the shortest path in a graph with $n$ vertices and $e$ edges is:

• A. $O(e)$
• B. $O(n)$
• C. $O(e^{2})$
• D. $O(n^{2})$

Comments

If the Graph is represented using Adjacency Matrix, it is $ O(V^2) $ . If the input graph is represented using adjacency list it can be reduced to $O(E log V)$ with the help of binary heap.

 Just replace E by $e$ and V by $ n$ to get your answer

Answer 1

answer is option D

Answer 2

Dijktra's algorithm's time complexity is     V.log(V) + E  (using fibonacci heaps). They have given #edges as 'e'. Now, 'e' can be equal to V*V. Also, the notation being used is big-O. So, answer is (D).

Answer 3

Undirected graph

BFS=O(V+E)=O(n+e)

Directed graph

dijkstra algorithm with list = O($V^{2}$)=O($n^{2}$)

dijkstra algorithm with binary heap=O((E+V)LOGV)=O((e+n)log(n))

dijkstra algorithm with fibbonacci heap=O((E+VLOGV)=O((e+nlog(n))

Bellman ford algorithm=O(VE)=(ne)

ANSWER SHOULD BE OPTION D