let us first assume that we are representing the graph using an adjacency list or adjacency map structure this data structure allows us to step through the vertices adjacent to during the relaxation step in time proportional to their number thereforethe time spent in the management of the nested for loopand the number of iterations of that loopis outdeg( ) in vg which is (mby proposition the outer while loop executes (ntimessince new vertex is added to the cloud during each iteration this still does not settle all the details for the algorithm analysishoweverfor we must say more about how to implement the other principal data structure in the algorithm--the priority queue referring back to code fragment in search of priority queue operationswe find that vertices are originally inserted into the priority queuesince these are the only insertionsthe maximum size of the queue is in each of iterations of the while loopa call to remove min is made to extract the vertex with smallest label from thenfor each neighbor of uwe perform an edge relaxationand may potentially update the key of in the queue thuswe actually need an implementation of an adaptable priority queue (section )in which case the key of vertex is changed using the method update( )where is the locator for the priority queue entry associated with vertex in the worst casethere could be one such update for each edge of the graph overallthe running time of dijkstra' algorithm is bounded by the sum of the followingn insertions into calls to the remove min method on calls to the update method on if is an adaptable priority queue implemented as heapthen each of the above operations run in (log )and so the overall running time for dijkstra' algorithm is (( mlog nnote that if we wish to express the running time as function of onlythen it is ( log nin the worst case let us now consider an alternative implementation for the adaptable priority queue using an unsorted sequence (see exercise - thisof courserequires that we spend (ntime to extract the minimum elementbut it affords very fast key updatesprovided supports location-aware entries (section specificallywe can implement each key update done in relaxation step in ( time--we simply change the key value once we locate the entry in to update hencethis implementation results in running time that is ( )which can be simplified to ( since is simple