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. Algorithms graph-algorithms shortest-path + – kallu singh asked Aug 20, 2017 retagged Jun 24, 2022 by makhdoom ghaya kallu singh 616 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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...???? rajoramanoj answered Aug 20, 2017 edited Aug 20, 2017 by rajoramanoj rajoramanoj comment Share Follow See all 3 Comments See all 3 3 Comments reply kallu singh commented Aug 20, 2017 reply Follow Share NO ALL THE GIVEN STATEMENTS ARE CORRECT 0 votes 0 votes kallu singh commented Aug 20, 2017 reply Follow Share but i don't know to how 0 votes 0 votes Anu007 commented Dec 15, 2017 reply Follow Share 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. true 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. false since when both are on same level then difference is 0 also 3. There is a path between a and b. true path is a-S then S-b if say direct path then no path. 0 votes 0 votes Please log in or register to add a comment.