# 7.21. Analysis of Dijkstra’s Algorithm¶

Finally, let’s look at the running time of Dijkstra’s algorithm. We
first note that building the priority queue takes \(O(|V|)\) time
since we initially add every vertex in the graph to the priority queue.
Once the queue is constructed, the `while`

loop
is executed once for every vertex since vertices are all added at the
beginning and only removed after that. Within that loop each call to
`delete`

takes \(O(\log{|V|})\) time. Taken together, that part of
the loop and the calls to `delete`

take \(O(|V| \times \log{|V|})\). The
`for`

loop is executed once for each edge in the
graph, and within the `for`

loop the call to `change_priority`

takes
\(O(|E| \times \log{|V|})\) time. So the combined running time is
\(O((|V|+|E|) \times \log{|V|}).\)

You have attempted of activities on this page