we currently have of the distance from to we initially have [ and set [zfor all vertices other than the start node then the algorithm repeatedly decreases the overestimates until it is no longer possible to decrease them further when this happensthe algorithm terminateswith each estimate fully constrained and said to be tight improving estimates the general idea is to look systematically for shortcuts suppose thatfor two given vertices and zit happens that [uweight[ ][zd[zthen there is way of going from to and then to whose total length is smaller than the current overestimate [zof the distance from to zand hence we can replace [zby this better estimate this corresponds to the code fragment if [uweight[ ][zd[zd[zd[uweight[ ][zof the full algorithm given below the problem is thus reduced to developing an algorithm that will systematically apply this improvement so that ( we eventually get the tight estimates promised aboveand ( that is done as efficiently as possible dijkstra' algorithmversion the first version of such an algorithm is not as efficient as it could bebut it is relatively simple and certainly correct (it is always good idea to start with an inefficient simple algorithmso that the results from it can be used to check the operation of more complex efficient algorithm the general idea is thatat each stage of the algorithm' operationif an entry [uof the array has the minimal value among all the values recorded in dthen the overestimate [umust actually be tightbecause the improvement algorithm discussed above cannot possibly find shortcut the following algorithm implements that idea/inputa directed graph with weight matrix 'weightand / start vertex ' /outputan array 'dof distances as explained above /we begin by buiding the distance overestimates [ /the shortest path from to itself has length zero for each vertex of the graph if is not the start vertex [zinfinity /this is certainly an overestimate /we use an auxiliary array 'tightindexed by the vertices/that records for which nodes the shortest path estimates /are ''known'to be tight by the algorithm for each vertex of the graph tight[zfalse