bos sfo dfw lax pvd bwi sfo dfw lax pvd jfk ord jfk bos ord bwi mia mia ( (jfigure an example execution of dijkstra' algorithm (continued from figure why it works the interesting aspect of the dijkstra algorithm is thatat the moment vertex is pulled into cits label [ustores the correct length of shortest path from to thuswhen the algorithm terminatesit will have computed the shortest-path distance from to every vertex of that isit will have solved the single-source shortest-path problem it is probably not immediately clear why dijkstra' algorithm correctly finds the shortest path from the start vertex to each other vertex in the graph why is it that the distance from to is equal to the value of the label [uat the time vertex is removed from the priority queue and added to the cloud cthe answer to this question depends on there being no negative-weight edges in the graphfor it allows the greedy method to work correctlyas we show in the proposition that follows proposition in dijkstra' algorithmwhenever vertex is pulled into the cloudthe label [vis equal to (sv)the length of shortest path from to justificationsuppose that [vd(svfor some vertex in and let be the first vertex the algorithm pulled into the cloud (that isremoved from qsuch that [zd(szthere is shortest path from to (for otherwise (szd[ ]let us therefore consider the moment when is pulled into cand let be the first vertex of (when going from to zthat 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 ythat is already in at this point