Question in Dijkstra's correctness condition 4

kaist-cp / cs500

Moved to https://cp-git.kaist.ac.kr/jeehoon.kang/cs500

25 stars 7 forks source link

Question in Dijkstra's correctness condition 4 #37

Closed CauchyComplete closed 5 years ago

CauchyComplete commented 5 years ago

Capture

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

HaritzPuerto commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

Gotcha