# Confused about the correctness proof of Dijkstra's algorithm

In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow:

Let u be v's predecessor on a shortest path P:s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (u, v) is relaxed, we have d(v) = δ(s,v), where the funciton δ(x, y) denotes the minimum path weight from x to y.

I wonder why we need the condition d(u) = δ(s,u) in this lemma. If Path P: s->...->u->v is a shortest path from s to v, then by the property of optimal substructure, the subpath s->...->u of P must also be a shortest path from s to u. Therefore, d(u) must equal to δ(s,u).

Does there exist the case that d(u) ≠ δ(s,u) but P: s->...->u->v is a shortest from s to v? If it does, can someone offer an example here.

Any help will be appreciated

PS: if you are interested in the entire proof. Check here, the proof starts at 45:30

It looks like you misunderstood the nature of $$d(v)$$ for a vertex $$v$$.

$$d(v)$$ is designed to hold the current known shortest distance from $$s$$ to $$v$$ at each step/stage of the algorithm. That is, $$d(v)$$ is not a fixed value given $$s$$ and $$v$$ alone.

At the start of Dijkstra's algorithm, $$d(s)$$ is initialized to 0 and $$d(v)$$ is initialized to $$\infty$$ for each vertex $$v\not=s$$ in $$G$$. For example, let graph $$G$$ have three vertices $$s, u, v$$ and two edges $$\{s,u\}, \{u,v\}$$. The path $$s,u,v$$ is a shortest path from $$s$$ to $$v$$. Right right after Dijkstra's algorithm has initialized $$d(u)$$ to $$\infty$$, we have $$d(u)=\infty\not=1=\delta(s,u)$$. This is one of the examples you are looking for. In fact, for all graphs in which $$u$$ is reachable from $$s$$, as long as $$d(u)$$ has not been relaxed to $$\delta(s,u)$$, we will have, of course, $$d(u)\not=\delta(s,u)$$.

On the other hand, $$d(u)=\delta(s,u)$$ must hold at the time when the edge $$(u, v)$$ is being relaxed in Dijkstra's algorithm. That might be the reason that prompts you to raise this question. Note that as a property of the Dijkstra's algorithm, that fact is not proved yet at the point of time in that lesson.