edited by
18,360 views
36 votes
36 votes

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 by

5 Answers

Best answer
49 votes
49 votes

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.

edited by
12 votes
12 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
6 votes
6 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

1 votes
1 votes

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.
Answer:

Related questions

21 votes
21 votes
7 answers
1
pC asked Dec 21, 2015
7,772 views
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...
24 votes
24 votes
4 answers
3
Kathleen asked Sep 21, 2014
10,765 views
Which of the following sorting algorithms has the lowest worse-case complexity?Merge sortBubble sortQuick sortSelection sort
27 votes
27 votes
4 answers
4
Kathleen asked Sep 21, 2014
13,758 views
Match the following:$$\begin{array}{llll} \text{(P)} & \text{SMTP} &(1)& \text{Application layer} \\ \text{(Q)} & \text{BGP}& (2) & \text{Transport layer} \\ \text{(R)}...