the first "wrongvertex picked picked implies that [ < [yc [zd(szs [xd(sxx [yd(syfigure schematic illustration for the justification of proposition moreoverd[xd(sx)since is the first incorrect vertex when was pulled into cwe tested (and possibly updatedd[yso that we had at that point [ < [xw(xyd(sxw(xybut since is the next vertex on the shortest path from to zthis implies that [yd(sybut we are now at the moment when we are picking znot yto join chenced[ < [yit should be clear that subpath of shortest path is itself shortest path hencesince is on the shortest path from to zd(syd(yzd(szmoreoverd(yz> because there are no negative-weight edges therefored[ < [yd(sy< (syd(yzd(szbut this contradicts the definition of zhencethere can be no such vertex the running time of dijkstra' algorithm in this sectionwe analyze the time complexity of dijkstra' algorithm we denote with and the number of vertices and edges of the input graph grespectively we assume that the edge weights can be added and compared in constant time because of the high level of the description we gave for dijkstra' algorithm in code fragment analyzing its running time requires that we give more details on its implementation specificallywe should indicate the data structures used and how they are implemented