outside the cloud that is closest to the algorithm terminates when no more vertices are outside the cloudat which point we have shortest path from to every other vertex of this approach is simplebut nevertheless powerfulexample of the greedy method design pattern greedy method for finding shortest paths applying the greedy method to the single-sourceshortest-path problemresults in an algorithm known as dijkstra' algorithm when applied to other graph problemshoweverthe greedy method may not necessarily find the best solution (such as in the so-called traveling salesman problemin which we wish to find the shortest path that visits all the vertices in graph exactly onceneverthelessthere are number of situations in which the greedy method allows us to compute the best solution in this we discuss two such situationscomputing shortest paths and constructing minimum spanning tree in order to simplify the description of dijkstra' algorithmwe assumein the followingthat the input graph is undirected (that isall its edges are undirectedand simple (that isit has no self-loops and no parallel edgeshencewe denote the edges of as unordered vertex pairs ( ,zin dijkstra' algorithm for finding shortest pathsthe cost function we are trying to optimize in our application of the greedy method is also the function that we are trying to compute--the shortest path distance this may at first seem like circular reasoning until we realize that we can actually implement this approach by using "bootstrappingtrickconsisting of using an approximation to the distance function we are trying to computewhich in the end will be equal to the true distance edge relaxation let us define label [ufor each vertex in vwhich we use to approximate the distance in from to the meaning of these labels is that [uwill always store the length of the best path we have found so far from to initiallyd[ and [ufor each uvand we define the set cwhich is our "cloudof verticesto initially be the empty set at each iteration of the algorithmwe select vertex not in with smallest [ulabeland we pull into in the very first iteration we willof coursepull into once new vertex is pulled into cwe then update the label [zof each vertex that is adjacent to and is outside of cto reflect the fact that there may be new and better way to get to via this update operation is known as relaxation procedurefor it takes an old estimate and checks if it can be improved to get closer to its true value ( metaphor for why we call this relaxation comes from spring that is stretched out and then "relaxedback to its true resting shape in the case of dijkstra' algorithmthe relaxation is performed for an edge ( ,zsuch