Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf about the performance of Dijkstra's algorithm on Page 118, we are given:
4.4.3 Running time
At the level of abstraction of Figure 4.8, Dijkstra's algorithm is structurally identical to breadth-first search. However, it is slower because the priority queue primitives are computationally more demanding than the constant-time
eject
's andinject
's of BFS. Sincemakequeue
takes at most as long as $|V|$insert
operations, we get a total of $|V|$deletemin
and $|V| + |E|$insert
/decreasekey
operations. The time needed for these varies by implementation; for instance, a binary heap gives an overall running time of $O((|V|+|E|)\log |V|)$.
I understand that it has $|V|$ insert
and deletemin
operations but can someone please explain why we have $|V|+|E|$ insert
/decreasekey
operations? First of of all, why does one algorithm have TWO kinds of insert operations? If they are the same kind, then where can we learn more about what decreasekey
actually does? The Wikipedia page doesn't seem to cover it much either (unless I missed or misunderstood it).