dijkstra' algorithm the main idea in applying the greedy method pattern to the single-source shortestpath problem is to perform "weightedbreadth-first search starting at the source vertex in particularwe can use the greedy method to develop an algorithm that iteratively grows "cloudof vertices out of swith the vertices entering the cloud in order of their distances from thusin each iterationthe next vertex chosen is the vertex outside the cloud that is closest to the algorithm terminates when no more vertices are outside the cloud (or when those outside the cloud are not connected to those within the cloud)at which point we have shortest path from to every vertex of that is reachable from this approach is simplebut nevertheless powerfulexample of the greedy method design pattern applying the greedy method to the single-sourceshortest-path problemresults in an algorithm known as dijkstra' algorithm edge relaxation let us define label [vfor each vertex in which we use to approximate the distance in from to the meaning of these labels is that [vwill always store the length of the best path we have found so far from to initiallyd[ and [vfor each sand 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 generalwe will use priority queue to select among the vertices outside the cloud in the very first iteration we willof coursepull into once new vertex is pulled into cwe then update the label [vof 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 the specific edge relaxation operation is as followsedge relaxationif [uw(uvd[vthen [vd[uw(uvalgorithm description and example we give the pseudo-code for dijkstra' algorithm in code fragment and illustrate several iterations of dijkstra' algorithm in figures through