MHB Proving $\delta(s,u)+w(u,v)=\delta(s,v)$ in a Shortest Path

[evinda]

Hey! (Blush)

I am looking at the proof of the following sentence:

Let $s \to u \to v$ a shortest path from the vertex $s$ to the vertex $v$.
Suppose that we relax at some time the edge $(u,v)$.If,before the call of Relaxation(u,v,w),it stands that $d=\delta(s,u)$,then after the call of Relaxation(u,v,w),it stands that $d[v]=\delta(s,v)$.

The algorithm of the function Relaxation(u,v,w) is the following:

Relaxation(u,v,w)
 if d[v]>d[u]+w(u,v)
    d[v]<-d[u]+w(u,v)
    p[v]<-u

This is the proof (Wait) :

If $d$ gets at some time the value $\delta(s,u)$,$d$ remains unchanged.After the relaxation,we have:

$$d[v] \leq d+w(u,v) \\ \ \ \ = \delta(s,u)+w(u,v) \\ \ \ \ = \delta(s,v)$$

So,we have: $d[v] \leq \delta(s,v)$.

However, it is known that $d[v] \geq \delta(s,v)$.

So,we conclude that $d[v]=\delta(s,v)$.

Could you explain me why $\delta(s,u)+w(u,v)=\delta(s,v)$ ? (Thinking)

 

[I like Serena]

Hi! (Smirk)

Could you explain me why $\delta(s,u)+w(u,v)=\delta(s,v)$ ? (Thinking)

Let $s \to u \to v$ a shortest path from the vertex $s$ to the vertex $v$.

Since $s \to u \to v$ is a shortest path, it follows that $\delta(s,u)+w(u,v)=\delta(s,v)$.

 

[evinda]

Hi! (Smirk)Since $s \to u \to v$ is a shortest path, it follows that $\delta(s,u)+w(u,v)=\delta(s,v)$.

I got it now! Thank you very much! (Smirk)