closed by
637 views
2 votes
2 votes
closed as a duplicate of: GATE CSE 2007 | Question: 41

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

   
   
 

(A) Dijkstra's algorithm starting from S

 

(B) Warshall's algorithm

 

(C) performing a DFS starting from S

 

(D) performing a BFS starting from S

closed by

2 Answers

1 votes
1 votes

Option D.

well, we know that the graph is unweighted means we have to just traverse through the graph.

When unweighted edges and shortest path given then you have to calculate minimum edge require reaching from S(Source) to D(Destination) Node.

Here, BFS is level order Traversal means, It will explore children of parent level by level.

So, let's say you are performing BFS from Node S then, It will first discover the closest node [distance is = 1 edge] from S. then all children of S will be explored next. After exploring children of S whatever nodes we will have They all are 2 edges away from S. this process will be repeated till we explore all the nodes. 

And if you will draw BFS tree then from Root all the nodes at level 1 are 1 edge distance away from S, Nodes at level 2 are 2 edge distance away from S, ... etc.

among options, we have option C and D have complexity lower than option A and B. but DFS is not suitable just because it is not level order traversal.

Related questions

2 votes
2 votes
1 answer
2
1 votes
1 votes
1 answer
3
Markzuck asked Jan 6, 2019
491 views
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?