Questions on Dijkstra’s Algorithm

Questions:

1. At most, how many times is the priority queue’s “push” method called?
   Answer

   |V| - the only time a vertex gets added is if it’s never been visited before and not in the frontier. Once it has been added to the priority queue, it will then always either be in the queue or it will have been visited.

2. At most, how many times is the priority queue’s “reduce_priority” method called?
   Answer

   |E| - in the worst case, each new edge we consider could be a better path and could cause a call to reduce_priority. Actually slightly less, because at least one edge per node will be the first path to that node, but that’s a reduction of at most |V| calls.

3. If implemented with a heap, what is the big-O runtime of “push?”
   Answer

   O(log n)

4. If implemented with a heap, what is the big-O runtime of “reduce_priority?”
   Answer

   O(log n)

5. If we assume that these calls are all the work Dijkstra’s algorithm does, what is the overall runtime of Dijkstra’s algorithm?
   Answer

   O( |V| log |V| + |E| log |V| ) = O( (|V| + |E|) log |V| ) - which intuitively makes sense since BFS and DFS are O(|V| + |E|) but have queue/stack implementations with constant-time operations.