Question in Dijkstra's correctness condition 4

[CauchyComplete]

Please explain how the condition 3 was used to prove Dv=D'v. Thanks

[HaritzPuerto]

Intuitively, I would say it is because Dv is not updated. D is only updated for N+G(f0), so Dv = D'v but I am not sure if this is rigorous enough. The 3rd condition states that if v \in X and w not \in X, then Dv <= Dw but it does not talk about what happens with the Dv, it does not state that the do not change, so I am not sure how to use condition 3 either

[jeehoonkang]

• Actually, I fixed a small typo. The second "v in X'" should be "v in X". I just committed the fix. Sorry.
• From the third condition, we know Dv <= D{f0} since v \in X and f0 \notin X. Then we have D'v = min(Dv, D{f0} + w_G(f0,v)) = Dv.

[CauchyComplete]

Gotcha