Dijkstra's algorithm: Difference between revisions

Revision as of 21:50, 9 December 2024

Revision as of 22:36, 9 December 2024

Line 175:

===Specialized variants===

When arc weights are small integers (bounded by a parameter <math>C</math>), specialized queues can be used for increased speed. The first algorithm of this type was Dial's algorithm{{Sfn|DIalDial|1969}} for graphs with positive integer edge weights, which uses a [[bucket queue]] to obtain a running time <math>O(|E|+|V|C)</math>. The use of a [[Van Emde Boas tree]] as the priority queue brings the complexity to <math>O(|E|\log\log C)</math> {{sfn|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}. Another interesting variant based on a combination of a new [[radix heap]] and the well-known Fibonacci heap runs in time <math>O(|E|+|V|\sqrt{\log C})</math> {{sfn|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}. Finally, the best algorithms in this special case run in <math>O(|E|\log\log|V|)</math>{{sfn|Thorup|2000}} time and <math>O(|E| + |V|\min\{(\log|V|)^{1/3+\varepsilon}, (\log C)^{1/4+\varepsilon}\})</math> time.{{sfn|Raman|1997}}

== Related problems and algorithms ==