Redirected
in Others edited by
932 views
1 vote
1 vote

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?

  1. $29$
  2. $27$
  3. $25$
  4. $17$
in Others edited by
932 views

4 Comments

0
0
Is $\mathbf{27}$ the answer?
0
0
$\mathbf{15+12 = 27}$
0
0
This question is directly asked from a standard textbook.
0
0

2 Answers

0 votes
0 votes

$\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

edited by
by

1 comment

27 is correct answer.
0
0
0 votes
0 votes

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]

 

Related questions