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

edited | 4.7k views
+3

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.

+1
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.

Dijkastra and Warshall 's algorithm used only 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 concerned in given question. So, BFS is answer.

Note :  Finding only path$(DFS)$ and finding shortest path$(BFS)$ matters a lot.

Correct Answer: $D$

by Boss (23.9k points)
edited
+6

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.

+20

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

+2
@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.
0
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
0
@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 !!!
0

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)

+1
yes
0
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!!!
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
by Boss (14.4k points)
+3
We can also use DFS algo implemented by Adjacency List data structure.It will also run in Linear time (V+E).
0
hi avdesh

What time does dijkastra would take?

regards

piyush
0
@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.
+2

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.

0
only BFS is correct..DFS is not applicable for undirected graph.and dijkstra and floyed not applicable to un weighted also..
+1
Who said DFS is not applicable to undirected graph ? It is possible to apply DFS on an undirected graph.

* 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|)

by Loyal (10k points)
+1
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) ?

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.
by Loyal (7k points)