The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.5k views

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

  1. Dijkstra’s algorithm starting from $S$.

  2. Warshall’s algorithm.

  3. Performing a DFS starting from $S$.

  4. Performing a BFS starting from $S$.

asked in Algorithms by Veteran (69k points)
edited by | 2.5k views

 

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.

3 Answers

+19 votes
Best answer

Dijkastra and warshall 's algo only used for weighted graph.

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 concern in given question so BFS is Ans.

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

answered by Veteran (23.4k points)
edited by

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 !!!
+10 votes
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
answered by Veteran (14.3k points)
We can also use DFS algo implemented by Adjacency List data structure.It will also run in Linear time (V+E).
hi avdesh

 

What time does dijkastra would take?

 

regards

piyush
@Arjun Sir which us correct out of c and d. I think both. BFS has time complexity O(V+E) and DFS has O(V+E) using Adjacency list.

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.
+4 votes

 * 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

answered by Boss (8.3k points)
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) ?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
114,178 comments
38,665 users