bfs dfs

Question

Which of the following statements is/are correct?

Consider 'n' as the number of nodes in graph.

A.In an unweighted, undirected connected graph, Dijkstra’s algorithm can be used to compute shortest path from node S to all the other vertices.

B.Bellman’s ford algorithm always detects a negative weighted cycles if it exists.

C.The time complexity of Dijkstra’s algorithm using unsorted array for the greedy selection of vertices and adjacency matrix is theta(n^2)

D.The time complexity of Bellman’s ford algorithm is always theta(n^3)

Answer 1

A.  Wrong  .  because for Dijkstra’s we need a edge weight .    or to find single source shortest path of  unweighted BFS is used.

 

B.   Wrong .  because Bellman’s ford algorithm can detect the negative edge weight cycle reachable from source. 

  

 

C .  right 

        time complexity of Dijkstra’s using unsorted array and with adjacency matrix of

        (n vertices and e edges) =  Ɵ(n²)  + Ɵ(n²)  + Ɵ(e) 

                                               =  Ɵ(n²) 

D    right :   because in all case time complexity of   Bellman’s ford algorithm  is   Bellman’s ford Ɵ(n³)

 

 

 ans : C , D