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$
  • $\begingroup$ one update per edge for all v vertex. so E/V? $\endgroup$ – Davied Zuhraph Nov 27 '20 at 15:33
  • $\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$ @Pseudonym would you please post as an answer and add some details about why amortized analysis relate to just fib,. heap not others method? $\endgroup$ – Davied Zuhraph Nov 29 '20 at 15:29
  • $\begingroup$ @Pseudonym would you please submit as an answer to check? $\endgroup$ – Davied Zuhraph Dec 2 '20 at 2:54
  • $\begingroup$ @DaviedZuhraph what do you mean by $O(E/V)$? Note that in Dijkstra's algorithm there are $|E|$ update operations and $|V|$ remove_min operations. Therefore, if you use the fib.heaps then the Dijkstra's algorithm would have total running time: $ |E| \cdot O(1) + |V| \cdot O(\log |V|) = O( |E| + |V| \log |V|)$. This complexity is better than complexity if you use any other data-structure that you have mentioned in the table. $\endgroup$ – Inuyasha yagami Jan 6 at 16:48
0
$\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$
  • $\begingroup$ so you means for answer to this question we should always know about all implementation ? $\endgroup$ – Davied Zuhraph Jan 7 at 20:44
  • $\begingroup$ @DaviedZuhraph I have added more details in my answer. Hope it will be helpful now. $\endgroup$ – Inuyasha yagami Jan 8 at 5:33
  • $\begingroup$ is there any references that tell us there is at most |E| updates on vertexes do in whole running of Dijkstra? $\endgroup$ – Davied Zuhraph Jan 9 at 23:47
  • $\begingroup$ @DaviedZuhraph I would suggest you read Section 24.3 (Dijkstra's algorithm) of CLRS. In fact, CLRS is an excellent source for many Graph Algorithms. $\endgroup$ – Inuyasha yagami Jan 10 at 5:45
  • $\begingroup$ I check it. nothing about this bound for update. please help me. $\endgroup$ – Davied Zuhraph Jan 10 at 11:34

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.