0 votes 0 votes The time required to find the shortest path in a graph with $n$ vertices and $e$ edges is: $O(e)$ $O(n)$ $O(e^{2})$ $O(n^{2})$ Others ugcnetcse-june2007-paper2 + – go_editor asked Mar 28, 2020 • edited May 21, 2021 by soujanyareddy13 go_editor 1.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply mcjoshi commented Aug 24, 2016 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes answer is option D vidhuc answered Aug 24, 2016 vidhuc comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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). Sushant Gokhale answered Aug 24, 2016 Sushant Gokhale comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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 Mohit Kumar 6 answered May 5, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.