1
$\begingroup$

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 and inject's of BFS. Since makequeuetakes 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).

Improve this question
$\endgroup$
1
  • $\begingroup$ Note: Dijkstra, not Dijstake. If it helps, it's pronounced "DEEK-struh" or, more often in English-speaking countries (but less authentically), "DIKE-struh". $\endgroup$
    – David Richerby
    Jan 25, 2019 at 14:58

2 Answers 2

Reset to default
0
$\begingroup$

Since makequeue takes at most as long as $|V|$ insert operations, we get a total of $|V|$ deletemin and $|V | + |E|$ insert/decreasekey operations.
First of of all, why one algorithm has TWO kinds of insert operations, if they are the same kind, then where can we learn more about what decreasekey actually does?

No, there is only one kind of insert operation. We got

  • $|V|$ deletemin operations.
  • a total of at most $|V|+|E|$ operations, where each operation is either an insert operation or a decreasekey operation. We count these two kinds of operations together because it takes the same asymptotic time to do either one of them, $O(\log |V|)$. More specifically. we have
    • |V| insert operations during makequeue.
    • at most |E| decreasekey operations as each edge may or may not lead to a decreasekey operation.
Improve this answer
$\endgroup$
5
  • $\begingroup$ Ok, we only have one kind of insert operation, which as the book pointed out, |V| insert. Then you explain that "we got a total of |V|+|E| operations, where each operation is either insert operation or decreasekey besides |V| deletemin" Is the |V| insert operations included in the |V|+|E| operations? Seem like (|V|+|E| ) include the insert operation and decreasekey operations, and |E| is counted as all vertices performed decreasekey operations on its edges as @desiredeveloper pointed out ? $\endgroup$
    – user94430
    Jan 25, 2019 at 19:09
  • $\begingroup$ Yes, $|E|$ is counted as each edge may (or may not) lead to a decreasekey operation. Please check my updated answer. Is it clear now (Please forget desiredeveloper's answer for the moment, since it is not easy to follow his answer as he made several suspicious or incorrect arguments.) $\endgroup$
    – John L.
    Jan 25, 2019 at 19:53
  • $\begingroup$ Now, you are making it more interesting. Can you please give an example when an edge is led to decreasekey, and an example is not.? $\endgroup$
    – user94430
    Jan 26, 2019 at 0:12
  • $\begingroup$ For example, in Figure 4.9, each of the edges $AB, AC,CB,CD,CE,BD, BE$ leads to decreasekey while none of the rest of edges, $BC, ED$ does. $\endgroup$
    – John L.
    Jan 26, 2019 at 0:35
  • $\begingroup$ yes. I did actually run through code, but first time learning it just didn't recall when you point out( as I didn't catch that detail) , but now re-visiting it makes more sense, Thank you.. $\endgroup$
    – user94430
    Jan 26, 2019 at 1:59
0
$\begingroup$

In worst case the number of delete operations are bounded by O(V) and now for each delete operation you perform on each vertex you may have to perform in worst case O(V-1) decrease-key operation as it may be adjacent to V-1 vertex considering a complete graph. Now total number of decrease key operations are bounded by O(E).

vertex 1 ---> v-1 decrease key (1 vertex removed from heap,added to visited)

vertex 2 ---> v-2 decrease key (2 vertex removed from heap,added to visited)

vertex 3 ---> v-3 decrease key

vertex 4 ---> v-4 decrease key

.

.

.

vertex |V| ---> 1 decrease key

total decrease key operations = $1+2+.....+(V-1) = O(V^2) = O(E)$

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am afraid that $O(V^2)\not=O(E)$. There are a couple of other suspicious or incorrect arguments. $\endgroup$
    – John L.
    Jan 25, 2019 at 7:46
  • $\begingroup$ can you please provide an instance when the equality doesn't hold? For connected graph we can have maximum of $O(V^2)$ edges hence is bounded. $\endgroup$
    – Shreyansh Jain
    Jan 25, 2019 at 12:49
  • $\begingroup$ It should be the other way around, $O(|E|)=O(|V|^2)$. Suppose the graph is a tree. Then $|E|=|V|-1$. $\endgroup$
    – John L.
    Jan 25, 2019 at 13:50
  • $\begingroup$ @desiredeveloper, so as you pointed out, The |E| of ( |V|+|E| ) insert/decreasekey comes from the sum of each vertex's edges? In other word, we iterate each vertex's edge to preform decreasekey? $\endgroup$
    – user94430
    Jan 25, 2019 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.