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?
For extended read.
A nice pdf:
http://www.columbia.edu/~cs2035/courses/csor4231.S19/sp.pdf
$\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
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]
64.3k questions
77.9k answers
244k comments
80.0k users