1 votes 1 votes 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? $29$ $27$ $25$ $17$ Others ugcnetcse-dec2019-paper2 + – soujanyareddy13 asked May 12, 2021 • edited May 29, 2021 by soujanyareddy13 soujanyareddy13 978 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply `JEET commented Dec 26, 2019 reply Follow Share For extended read. A nice pdf: http://www.columbia.edu/~cs2035/courses/csor4231.S19/sp.pdf 0 votes 0 votes `JEET commented Dec 26, 2019 reply Follow Share Is $\mathbf{27}$ the answer? 0 votes 0 votes `JEET commented Dec 26, 2019 reply Follow Share $\mathbf{15+12 = 27}$ 0 votes 0 votes `JEET commented Dec 26, 2019 reply Follow Share This question is directly asked from a standard textbook. 0 votes 0 votes Please log in or register to add a comment.
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 `JEET answered Dec 26, 2019 • edited Dec 26, 2019 by `JEET `JEET comment Share Follow See 1 comment See all 1 1 comment reply Udhay Brahmi commented Apr 9, 2022 reply Follow Share 27 is correct answer. 0 votes 0 votes Please log in or register to add a comment.
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] chirudeepnamini answered May 16, 2021 chirudeepnamini comment Share Follow See all 0 reply Please log in or register to add a comment.