Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 10:49, 9 January 2020

Revision as of 00:17, 10 January 2020

Line 16:

{{archives|auto=long|search=yes|bot=MiszaBot I|age=365}}

{{merged from|Uniform-cost search}}

== Terminological Dissonance? ==

The terminology in the caption for the animation is not in full agreement with the description of the algorithm: (a) the algorithm description does not mention a "tentative set" - it does mention "tentative distances", and it mentions an "unvisited set"; (b) the algorithm description mentions no "heuristic", but the caption to the animation says that the algorithm uses a "heuristic that is identically zero". At first it seemed to me that the caption of the animation intended "tentative set" to mean that which is meant by "unvisited set" in the algorithm description, but as I thought about it, I am unsure; on the other hand, it seems clear to me that even if that is not the intent of the caption, it '''does''' follow that the "tentative set" is identical to the "unvisited set" in that example. Matt Insall 13:15, 5 August 2017 (UTC) <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Espresso-hound|Espresso-hound]] ([[User talk:Espresso-hound#top|talk]] • [[Special:Contributions/Espresso-hound|contribs]]) </small> <!--Autosigned by SineBot-->

== Complexity with Fibonacci heaps ==

A few users have been changing the complexity with Fibonacci heaps from <math>O(|E| + |V| \log|V|)</math> to <math>O((|E| + |V|) \log|V|)</math> without any justification. The former appears to be correct based on the reasoning in the article:

:For any implementation of the vertex set {{mvar|Q}}, the running time is in

::<math>O(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em})</math>,

:where <math>T_\mathrm{dk}</math> and <math>T_\mathrm{em}</math> are the complexities of the ''decrease-key'' and ''extract-minimum'' operations in {{mvar|Q}}, respectively.

since <math>T_\mathrm{dk} = \Theta(1)</math> for Fibonacci heaps.

Hence I am reverting the complexity with Fibonacci heaps back to <math>O(|E| + |V| \log|V|)</math>. -- [[User:Paddu|Paddu]] ([[User talk:Paddu|talk]]) 15:44, 27 December 2017 (UTC)

== Is the algorithm description incorrect? ==