into the cloudthe label [uis equal to (vu)the length of shortest path from to justificationsuppose that [ ]> ( ,tfor some vertex in vand let be the first vertex the algorithm pulled into the cloud (that isremoved from qsuch that [ ]> ( ,uthere is shortest path from to (for otherwise (vu)= [ ]let us therefore consider the moment when is pulled into cand let be the first vertex of (when going from to uthat is not in at this moment let be the predecessor of in path (note that we could have (see figure we knowby our choice of zthat is already in at this point moreoverd[yd( , )since is the first incorrect vertex when was pulled into cwe tested (and possibly updatedd[zso that we had at that point [ ]<= [ ]+ (( , ))= ( , )+ (( , )but since is the next vertex on the shortest path from to uthis implies that [zd( ,zbut we are now at the moment when we are picking unot zto join chenced[ <= [zit should be clear that subpath of shortest path is itself shortest path hencesince is on the shortest path from to ud( , )+ ( , )= ( ,umoreoverd(zu> because there are no negative-weight edges therefored[ < [zd( , < ( ,zd( ,ud( ,ubut this contradicts the definition of uhencethere can be no such vertex figure schematic illustration for the justification of proposition