/all entries in the array 'tighthold the value true repeat as many times as there are vertices in the graph find vertex with tight[ufalse and minimal estimate [utight[utrue for each vertex adjacent to if [uweight[ ][zd[zd[zd[uweight[ ][ /lower overestimate exists /at this pointall entries of array 'dhold tight estimates it is clear that when this algorithm finishesthe entries of cannot hold under-estimates of the lengths of the shortest paths what is perhaps not so clear is why the estimates it holds are actually tighti are the minimal path lengths in order to understand whyfirst notice that an initial sub-path of shortest path is itself shortest path to see thissuppose that you wish to navigate from vertex to vertex zand that the shortest path from to happens to go through certain vertex then your path from to can be split into two pathsone going from to (an initial sub-pathand the other going from to ( final sub-pathgiven that the wholeunsplit path is shortest path from to zthe initial sub-path has to be shortest path from to ufor if notthen you could shorten your path from to by replacing the initial sub-path to by shorter pathwhich would not only give shorter path from to but also from to the final destination now it follows that for any start vertexthere is tree of shortest paths from that vertex to all other vertices the reason is that shortest paths cannot have cycles implicitlydijkstra' algorithm constructs this tree starting from the rootthat isthe start vertex ifas tends to be the case in practicewe also wish to compute the route of shortest pathrather than just its lengthwe also need to introduce third array pred to keep track of the 'predecessoror 'previous vertexof each vertexso that the path can be followed back from the end point to the start point the algorithm can clearly also be adapted to work with non-weighted graphs by assigning suitable weight matrix of for connected vertices and for non-connected vertices the time complexity of this algorithm is clearly ( where is the number of verticessince there are operations of (nnested within the repeat of (na simple example suppose we want to compute the shortest path from (node to (node in the weighted graph we looked at before