0
$\begingroup$

I see the following image on google:

enter image description here

And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should used sorted array or binary heap for implementation? non of others get us this Amortized Cost?

$\endgroup$
1
  • $\begingroup$ Yes, and therefore you want something with $O(1)$ update. This is why Fibonacci heaps are the usual tool of choice. $\endgroup$ – Pseudonym Nov 29 '20 at 13:41
1
$\begingroup$

In Dijkstra's algorithm there are $|E|$ update operations and $|V|$ remove_min operations.

To implement the algorithm, we can employ different types of data-structures. Since you are looking for the best update cost per vertex, you can employ the Fibonacci heap or Hash map implementation since they give you the minimum update cost (as per the table mentioned in your question). Now, suppose you employ Fibonacci heap. Then, the total amortized update cost for Dijkstra's algorithm would be $|E| \cdot O(1) = O(|E|)$. Therefore, the amortized update cost per vertex is: $O(|E|/|V|)$.


These are the three main implementations of Dijkstra's algorithm:

  1. Array Implementation (a.k.a. Hash Map as per your table): Update $O(1)$ and Remove_Min $O(|V|)$

  2. Binary Heap Implementation (a.k.a. Hybrid Binary Heap as per your table): Update $O(\log |V|)$ and Remove_Min $O(\log |V| )$

  3. Fibonacci Heap Implementation: Update Cost $O(1)$ and Remove_Min Cost $O(\log |V|)$

Note that Fibonacci Heap provides the best update cost and the best remove_min cost among these three options. Therefore, it is the best of both worlds. Hence, it is best for Dijkstra's algorithm and you can remember this implementation only.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.