comparing the two implementations we have two choices for implementing the adaptable priority queue with locationaware entries in dijkstra' algorithma heap implementationwhich yields running time of (( mlog )and an unsorted sequence implementationwhich yields running time of ( since both implementations would be fairly simple to codethey 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 nproposition given weighted graph with vertices and edgessuch that the weight of each edge is nonnegativeand vertex of gdijkstra' algorithm can compute the distance from to all other vertices of in the better of ( or (( mlog ntime we note that an advanced priority queue implementationknown as fibonacci heapcan be used to implement dijkstra' algorithm in ( log ntime programming dijkstra' algorithm in python having given pseudo-code description of dijkstra' algorithmlet us now present python code for performing dijkstra' algorithmassuming we are given graph whose edge elements are nonnegative integer weights our implementation of the algorithm is in the form of functionshortest path lengthsthat takes graph and designated source vertex as parameters (see code fragment it returns dictionarynamed cloudmapping each vertex that is reachable from the source to its shortest-path distance (svwe rely on our adaptableheappriorityqueue developed in section as an adaptable priority queue as we have done with other algorithms in this we rely on dictionaries to map vertices to associated data (in this casemapping to its distance bound [vand its adaptable priority queue locatorthe expected ( )-time access to elements of these dictionaries could be converted to worst-case boundseither by numbering vertices from to to use as indices into listor by storing the information within each vertex' element the pseudo-code for dijkstra' algorithm begins by assigning [vfor each other than the source we rely on the special value floatinf in python to provide numeric value that represents positive infinity howeverwe avoid including vertices with this "infinitedistance in the resulting cloud that is returned by the function the use of this numeric limit could be avoided altogether by waiting to add vertex to the priority queue until after an edge that reaches it is relaxed (see exercise -