are as followsinserting all the vertices in with their initial key value can be done in ( logntime by repeated insertionsor in (ntime using bottom-up heap construction (see section at each iteration of the while loopwe spend (logntime to remove vertex from qand (degree( )log ntime to perform the relaxation procedure on the edges incident on the overall running time of the while loop is which is (( +mlog nby proposition note that if we wish to express the running time as function of onlythen it is ( log nin the worst case an alternative implementation for dijkstra' algorithm let us now consider an alternative implementation for the adaptable priority queue using an unsorted sequence thisof courserequires that we spend (ntime to extract the minimum elementbut it allows for 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 comparing the two implementations we have two choices for implementing the adaptable priority queue with location-aware entries in dijkstra' algorithma heap implementationwhich yields running time of (( )log )and an unsorted sequence implementationwhich yields running time of ( since both implementations would be fairly simple to code upthey are about equal in terms of the programming sophistication needed these two implementations are also about equal in terms of the constant factors in their worst-case running times looking only at these worst-case timeswe prefer the heap implementation when the number of edges in the graph is small (that iswhen /log )and we prefer the sequence implementation when the number of edges is large (that iswhen /log