Confused about the proof of Dijkstra Algorithm

user_2978010 0
Viewed 261

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 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.

shortest-path dijkstra graph algorithm
1 Answers

Yes, we must need that lemma. When we are running the algorithm, distance to u is changing until we got a shortest distance to u. For example, if u is reached by some node a, and distance from s to u via a is d(u) but not optimal, and later in the algorithm. We found out that from s to u via b is the shortest path. So at this point, d(u) becomes the optimal.

Hope this helps.

user_133571700
Related