Register

GO Classes DPP | Algorithms | BFS

466 views
3 3 votes

Consider an undirected, weighted graph G with positive weights. Let a breadth-first traversal of G be done starting from a node r.

Let $d(r, u), d(r, v)$ represent the length of the shortest path from $r$ to $u, v$ respectively.

If u is visited before v during the traversal, which of the following must hold?

  1. $d(r, u)<d(r, v)$
     
  2. $d(r, u) \leq d(r, v)$
     
  3. $d(r, u) \geq d(r, v)$
     
  4. None of the above

2 Answers

0 0 votes
answer is   D becuse it weighted graph but if weights are contant then  B and c is correct  deppend on which node visited first is correct.
0 0 votes

BFS ignores weight, it only minimizes the number of edges not the sum of weight. Hence $(D)$

  • Either u is in a lower BFS level than v, or
  • u and v are in the same BFS level but u was dequed earlier
One more point, its BFS thus can't use Parenthesis Theorem, cause if the same question was for DFS then it can be easily solved by Parenthesis Theorem.
Voting & Accepting an answer helps improve the community
← Previous · GO Classes DPP | Alg...Next → · GO Classes DPP | Alg...
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

2 2 votes
2 2 answers
632
632 views
GO Classes asked Sep 4, 2025
632 views
GO Classes DPP | Algorithms | Tournament method
In a tournament method with $8$ distinct elements, suppose elements are inserted in random order into the knockout tree to find max, $2^{\text {nd }} \max$. What is the p...
1 1 vote
2 2 answers
384
384 views
GO Classes asked Sep 4, 2025
384 views
GO Classes DPP | Algorithms | Tournament method
Which of the following statement(s) is/are correct?Tournament method always requires fewer comparisons than linear scan for any $\mathrm{n}>2$ while finding the max and s...
2 2 votes
2 2 answers
356
356 views
GO Classes asked Sep 4, 2025
356 views
GO Classes DPP | Algorithms | DFS
Consider a directed graph $G=(V, E)$, where$\mathrm{V}=\{1,2, \ldots, 40\}$ For every vertex $u$, there is an edge $(u, v)$ iff $v=2 u$ or $v=2 u+1$Suppose the adjacency ...
1 1 vote
2 2 answers
377
377 views
GO Classes asked Sep 4, 2025
377 views
GO Classes DPP | Algorithms | DFS
Consider the following undirected graph:Which of the following is/are not correct DFS traversal sequences of the above graph starting from the vertex 3 (Assume the adjace...