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
inject's of BFS. Since
makequeuetakes at most as long as $|V|$
insertoperations, we get a total of $|V|$
deleteminand $|V| + |E|$
decreasekeyoperations. 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|$
deletemin operations but can someone please explain why we have $|V|+|E|$
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).