in this sectionwe analyze the time complexity of dijkstra' algorithm we denote with and mthe number of vertices and edges of the input graph grespectively we assume that the edge weights can be added and compared in constant time because of the high level of the description we gave for dijkstra' algorithm in code fragment analyzing its running time requires that we give more details on its implementation specificallywe should indicate the data structures used and how they are implemented let us first assume that we are representing the graph using an adjacency list structure this data structure allows us to step through the vertices adjacent to during the relaxation step in time proportional to their number it still does not settle all the details for the algorithmhoweverfor we must say more about how to implement the other principle data structure in the algorithm--the priority queue an efficient implementation of the priority queue uses heap (section this allows us to extract the vertex with smallest label (call to the removemin methodin (logntime as noted in the pseudo-codeeach time we update [zlabel we need to update the key of in the priority queue thuswe actually need heap implementation of an adaptable priority queue (section if is an adaptable priority queue implemented as heapthen this key update canfor examplebe done using the replacekey(ek)where is the entry storing the key for the vertex if is location-awarethen we can easily implement such key updates in (logntimesince location-aware entry for vertex would allow to have immediate access to the entry storing in the heap (see section assuming this implementation of qdijkstra' algorithm runs in (( mlogntime