retagged by
925 views
1 votes
1 votes

We are provided with an undirected connected graph such that weight of all the edges is equal to some constant k. We wish to find the shortest distance between given pair of nodes. Which of the following statements is(are) true?

I. We can use Depth First Search to determine the length of the shortest path between the pair of nodes.
II. We can use Breadth First search to find the desired answer.
III. Breadth First Search will give the correct answer only if the given graph is a tree.
IV. Depth First Search will give the correct result only if the given graph is a tree.

  1. Only I and II
  2.  Only II and IV
  3. Only III and IV
  4.  Only II and III
retagged by

2 Answers

Best answer
2 votes
2 votes

 We are provided with an undirected connected graph such that weight of all the edges is equal to some constant k. We wish to find the shortest distance between given pair of nodes.

Now we know that BFS is used to find the shortest distance between one node to every other node no matter it contains cycle or not Time will be O(e+v) only.

Now Take each statement:

I. We can use Depth First Search to determine the length of the shortest path between the pair of nodes.  It may be the case DFS fails i.e. when a graph has cycle then DFS may result incorrect i.e.

It can give distance between 2 - 5 as 2,1,4,3,5 = 4  which is incorrect , correct is 2,6,5 = 2.
II. We can use Breadth First search to find the desired answer. This is true since we go level by level so we will get the shortest path between every other node from a particular node.

III. Breadth First Search will give the correct answer only if the given graph is a tree. This is note true since for cyclic graph also we will get correct answer.


IV. Depth First Search will give the correct result only if the given graph is a tree. This is true since there is no cycle in graph i.e.tree so we have only one way to reach desired node i.e. we will get correct distance only.

selected by
0 votes
0 votes

Shortest distance of a graph can be found, when the graph forms a Minimum Spanning tree.(MST).

BFS is one of the way to find the path in tree format and definition of MST  is

"If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Minimum Spanning Tree". !

for more https://gateoverflow.in/3550/gate2006-it-11

Related questions

0 votes
0 votes
0 answers
1