GATE CSE 2007 | Question: 41

Question

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$.

Comments

DFS always not gives shortest paths in an undirected graph. BFS should be the correct choice here.

for example, consider a graph formed by taking the corners of a triangle and connecting them. If you try to find the shortest path from one node to another using DFS, then you will get the wrong answer unless you follow the edge directly connecting the start and destination nodes.

---

catch here is given that unweighted graph, this is one property of bfs to give shortest path only when graph is unweigted .if graph is weighted then bfs fail.

---

Similar question : Algorithms: GATE CSE 2006 | Question: 12 (gateoverflow.in)

---

D

Answer 1

Dijkstra’s and Warshall's algorithms are used only for weighted graphs.

Both DFS and BFS can be used for finding path between $2$ vertices in undirected and unweighted graph but BFS can only give the shortest path as concerned in given question. So, BFS is answer.

Note :  Finding only path (DFS) and finding shortest path (BFS) matters a lot.
 
Must Read: https://www.quora.com/What-are-the-advantages-of-using-BFS-over-DFS-or-using-DFS-over-BFS-What-are-the-applications-and-downsides-of-each

Correct Answer: D.

Comments

Though it is unweighted Graph;  DFS  may not give you shortest path (but can give a path)where as BFS will always give u Shortest Path .

Take a unweighted graph run BFS & DFS u will realize this fact soon. Ex. Suppose u want to find shortest path between A & D then DFS may visit A-B-E-C-D(cost 4)

While BFS only visit A-D(cost 1-Shortest)

Note:- Though here weight is not specified u can count no. of edges.

---

Your conclusion is correct but example is wrong.

for graph G, one of the DFT is fig-1, which says path from A to C is 2 length, while BFT always says path from A to C is one length

---

@Rajesh Pradhan, the graph u provided will give shortest distance between any two vertices same in BFS and DFS. The only difference is some distances in BFS are calculated earlier than DFS (like in ur ex., A to D in BFS may be earlier than DFS, if DFS chooses B last.). And some distances in DFS are calculated earlier than BFS(like A to E computation will be earlier if DFS chooses B first.)

As the graph u provided is tree, so there is only one distance exists. U can use any algorithm, Both will give same answer.

---

Actually I had made the example by myself from the conlusion Cz i was not able to find any example which shows me path finding using bfs and dfs.

So plz provide me any source which talks about ur claim.

Thanks

---

@Sachin Mittal Sir in ur given example r u showing in the Graph G there is a Direct connection between A and C ? Pls do reply Sir if possible !!!

---

Can we also add one more comment to Sachin sir comment ->

BFS not gives the shortest path between two pair of vertices.

It can clearly seen from the e.g. given by Sachin sir that dist(B,C) = 1(edge) but BFS gives it 2(edge) isn't it ? (I consider undirected graph bcoz it's also true for it)

---

yes

---

BFS actually gives the single source shortest path from the starting node to all the other nodes in the Graph...

Correct me if I am wrong!!!

---

Doubt Solved :)

---

@Sachin Mittal1  Sir, 

The only difference is some distances in BFS are calculated earlier than DFS (like in ur ex., A to D in BFS may be earlier than DFS, if DFS chooses B last.). And some distances in DFS are calculated earlier than BFS(like A to E computation will be earlier if DFS chooses B first.)

isn’t DFS chooses B first. ??

---

@ASNR1010 Yes you are correct. It should be DFS chooses B first.​@Sachin Mittal 1 Sir.

---

BFS has O(V+E) thats true, but in the worst case if the graph is a complete graph then E =V*(V-1)/2 right?
Does it mean its worst case is O(V^2)?? that way djikstra should be the answer. what do you say?

Answer 2

In BFS traversal .1st we note those vertices which can be reached directly from starting vertex..next we note the vertices which can be reached in 2 steps from starting vertex ..then as follows so it is the best choice i can make

Comments

Djikstra's and Warshall's algo have time complexities as $\Theta (|E| + |V| log |V|)$ and $\Theta (|V|^3)$ respectively. And DFS and BFS are linear.

With DFS we might not get shortest path. Assume some node that is at distance 1 from parent node, and 2 from child node. Since we traverse the child node first and then the neighbors, child node with distance 2 will be selected as shortest path, and path of distance 1 will be ignored, as the node is already traversed in DFS through child node first.

Now, in case BFS, the idea is simple, traverse all nodes at distance 1 from source, then traverse all the nodes that are at distance 2 from source and so on. Hence shortest distance is guaranteed.

Hence D is the answer

---

only BFS is correct..DFS is not applicable for undirected graph.and dijkstra and floyed not applicable to un weighted also..

---

Who said DFS is not applicable to undirected graph ? It is possible to apply DFS on an undirected graph.

Answer 3

 * Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E) 
* Time Comlexity of the Warshall’s algorithm is O(|V|^3)
* DFS cannot be used for finding shortest paths
* BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

Answer D

Comments

Dijkstra's algorithm, implemented using heap data structure would give the time complexity as O(V+E (Log V) )

Which implementation would give its TC as O(V^2 +E) ?

---

@rishi71662data4 its array based implementation where extract min is $O(V)$ and decrease key $O(1)$

---

Different Implementations

$A.L + Min heap --> O(E+V)logV$

$A.M + Min heap --> O(V^2 + E.logV)$

$A.L + Unsorted Array --> O(V^2)$

$A.M + Sorted Array --> O(V^2 + E.V)$

 

---

BFS has O(V+E) thats true, but in the worst case if the graph is a complete graph then E =V*(V-1)/2 right?
Does it mean its worst case is O(V^2)?? that way djikstra should be the answer.@Deepak Poonia sir what do you say?

Answer 4

Dijkstra runs in O(E log V) time. //Time complexity is different when Data Structures used are different)

BFS runs in O(E + V) time. //adjacency list.

A BFS can be seen as a lightweight version of Dijkstra's algorithm, that can handle only unweighted graphs (or the graphs in which each edge weighs equally; same thing)

Option D

---

Other uses of BFS/DFS:-

• Checking if the graph is connected. And, finding connected components — also can find the number of nodes in a connected component. It can also check if a graph is cyclic or acyclic. Also, for topological sorting. (DFS can do all this, too)
   
• DFS can be used to find cut edges and vertices.
   
• BFS can be used as a lightweight version of Dijkstra. It can also check if a graph is bipartite.

Comments

Djikstra's is just BFS with the queue replaced with a priority queue.

Answer 5

Time Complexity of the Dijkstra’s algorithm : It depends on your implementation of Dijkstra's Algorithm. Simple algorithm is given below with Time complexity of O(V2). There are also some time-efficient Algorithms: Graph represented using adjacency list can be reduced to O(E log V) with the help of binary heap.

Time Complexity of the Warshall’s algorithm: O(n3). Warshall’s algorithm basically we are using to find all pair shortest path.

 DFS cannot be used for finding shortest paths.

Time Complexity for BFS : O(E+V)