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