GATE CSE 2015 Set 1 | Question: 45

Question

Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the resultant BFS tree. If $(u, v)$ is an edge of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$?

• A. $-1$
• B. $0$
• C. $1$
• D. $2$

Comments

Edges of $G$ which are not in $T$ are $(t-x),(x-u),(u-y)$

Option $A,B,C$ Satisfied

Answer $:D$

---

The simplest logic is since there is edge between u  and v in  even u is at 100 units  then v will be at 101 logically as there is and edge so distance cannot be  2 in anyway

---

Q8 here https://inst.eecs.berkeley.edu/~cs170/fa18/assets/exams/fa17-sol.pdf

Answer 1

NOTE IF QSN MENTION ABOUT SHORTEST PATH IS WEIGHTED GRAPH
 THEN ALL WEIGHTS ARE EQUAL


BECAUSE BFS NOT COMPUTE SHORTEST PATH FOR DIFFERENT WEIGHTS GRAPH


SO IN EXAMPLE TAKE ALL WEIGHTS AS EQUAL U WILL FIND OPTION D AS CORRECT

Answer 2

Option D is correct option