UGC NET CSE | December 2019 | Part 2 | Question: 40

Question

Consider a weighted directed graph. The current shortest distance from source $S$ to node $x$ is represented by $d[x]$. Let $d[v] =29$, $d[u]=15$, $w[u,v]=12$. What is the updated value of $d[v]$ based on current information?

• A. $29$
• B. $27$
• C. $25$
• D. $17$

Comments

For extended read.

A nice pdf:

http://www.columbia.edu/~cs2035/courses/csor4231.S19/sp.pdf

---

Is $\mathbf{27}$ the answer?

---

$\mathbf{15+12 = 27}$

---

This question is directly asked from a standard textbook.

Answer 1

$\underline{\textbf{Answer:}}\Rightarrow27$

$\underline{\textbf{Explanation:}}\Rightarrow$

If $\mathbf{d}$ represents the length of the path, then:

$\mathrm{\mathrm{d(v) =\begin{cases}0, &\text{if $\mathrm{v=s}$, }\\\mathrm{\displaystyle\min_{u:(u,v)\in E}\{d(u) + w(u,v)\}}, &\text{otherwise,}\end{cases}}}$

where $\mathbf{w(u,v)}$ is the weight of the edge $\mathbf{(u,v)}$.

 

$\therefore$ Here, $\mathbf{d(u) + w(u,v)} = 15 + 12 = 27$

$\therefore \mathbf{27}$ is the correct answer.

---

$\color{Magenta}{\textbf{For extended Read:}}\Rightarrow$

https://docs.google.com/viewer?url=http%3A%2F%2Fwww.columbia.edu%2F~cs2035%2Fcourses%2Fcsor4231.S19%2Fsp.pdf&embedded=true&chrome=false&dov=1

Comments

27 is correct answer.

Answer 2

From the given information, we can draw the following image.

After applying relaxation of edge u-v, the distance between the source S and node v reduces to 27.

Relax operation:

 if d[v]> d[u] + w[u.v]:
       d[v]=d[u]+ w[u.v]