Dijkstra's algorithm: Difference between revisions - Wikipedia

Line 187:

===Specialized variants===

When arc weights are integers and bounded by a constant ''C'', the usageuse of a special priority queue structure by [[Van Emde Boas ettree]] al.(1977)as {{harv|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}the priority queue brings the complexity to <math>O(|E|\log\log|C|)</math> {{harv|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}. Another interesting implementation 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> {{harv|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}. Finally, the best algorithms in this special case are as follows. The algorithm given by {{harv|Thorup|2000}} runs in <math>O(|E|\log\log|V|)</math> time and the algorithm given by {{harv|Raman|1997}} runs in <math>O(|E| + |V|\min\{(\log|V|)^{1/3+\epsilon}, (\log|C|)^{1/4+\epsilon}\})</math> time.

Also, for [[directed acyclic graph]]s, it is possible to find shortest paths from a given starting vertex in linear <math>O(|E|+|V|)</math> time, by processing the vertices in a [[Topological sorting|topological order]], and calculating the path length for each vertex to be the minimum length obtained via any of its incoming edges.<ref>http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html</ref><ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=655}}</ref>