Questions about the proof of correctness of Dijstra's Algorithm

[HaritzPuerto]

Hello,

I have a few questions about the proof of correctness of Dijkstra's Algorithm.

1. I do not understand why in the proof of the 5th condition we need to check the min between two things (see picture)

Df0 <= Df according to the algorithm, isn't it?

So why do we need to compute the min between f0 and other f in F-{f0}?

In the first equation, I guess it should be min (Dv, Df0 + wG(f0, v)) right?
In the second equation, I do not understand why X union F. According to the algorithm X' = X union {f0}, and I think there is a similar issue in the second condition of the IH, isn't it?

All elements in F except f0 have D = inf, right?

For me this proof is kind of difficult so I am not sure if I am understanding everything

Thanks!

[jeehoonkang]

1: We're calculating the minimum value of D_f + \delta_{G\X}(f,v) for f \in F, which may be D_f0 + \delta_{G\X}(f0,v) or not. In this step, we're just splitting the set F into {f0} and F \ {f0}.

2: Thank you for pointing out the typos. As you said, the conditions on D'_v and X' were wrong, and I just fixed them. But the second condition of the IH is correct. Once a vertex f is inserted to F, its D_f is also updated as well. See lines 10 and 12 of the algorithm.

[HaritzPuerto]

Thank you. It is clear now