retagged by
616 views
0 votes
0 votes
Question: 17  

Consider two vertices a and b that are simultaneously on the FIFO queue at same point during the execution of breadth first search from s in an undirected graph.
Which of the following is true?

1. The number of edges on the shortest path between s and a is atmost one more than the number of edges on the shortest path between s and b.

2. The number of edges on the shortest path between s and a is atleast one less than the number of edges on the shortest path between s and b.

3. There is a path between a and b.
retagged by

1 Answer

0 votes
0 votes

you can see the image given below

as shown in bft as single source shortest path

shortest dist b/w S and a = 2  

shortest dist b/w S and b = 2

and there is no path b/w a and b

@ arjun sir plz verify am i correct...????

edited by

Related questions

1 votes
1 votes
3 answers
2