Editing Dijkstra's algorithm (section)

===Using a priority queue===
A min-priority queue is an abstract data type that provides 3 basic operations: {{mono|add_with_priority()}}, {{mono|decrease_priority()}} and {{mono|extract_min()}}. As mentioned earlier, using such a data structure can lead to faster computing times than using a basic queue. Notably, [[Fibonacci heap]]{{sfn|Fredman|Tarjan|1984}} or [[Brodal queue]] offer optimal implementations for those 3 operations. As the algorithm is slightly different in appearance, it is mentioned here, in pseudocode as well:

 1   '''function''' Dijkstra(''Graph'', ''source''):
 2       Q ← Queue storing vertex priority
 3       
 4       dist[''source''] ← 0                          ''// Initialization''
 5       ''Q''.add_with_priority(''source'', 0)            ''// associated priority equals dist[·]''
 6
 7       '''for each''' vertex ''v'' in ''Graph.Vertices'':
 8           '''if''' ''v'' ≠ ''source''
 9               prev[''v''] ← UNDEFINED               ''// Predecessor of v''
 10              dist[''v''] ← INFINITY                ''// Unknown distance from source to v''
 11              Q.add_with_priority(v, INFINITY)
 12
 13
 14      '''while''' ''Q'' is not empty:                     ''// The main loop''
 15          ''u'' ← ''Q''.extract_min()                   ''// Remove and return best vertex''
 16          '''for each''' arc (u, v) :                 ''// Go through all v neighbors of u''
 17              ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
 18              '''if''' ''alt'' < dist[''v'']:
 19                  prev[''v''] ← ''u''
 20                  dist[''v''] ← ''alt''
 21                  ''Q''.decrease_priority(''v'', ''alt'')
 22
 23      '''return''' (dist, prev)

Instead of filling the priority queue with all nodes in the initialization phase, it is possible to initialize it to contain only ''source''; then, inside the <code>'''if''' ''alt'' < dist[''v'']</code> block, the {{mono|decrease_priority()}} becomes an {{mono|add_with_priority()}} operation.<ref name=" mehlhorn" />{{rp|198}}

Yet another alternative is to add nodes unconditionally to the priority queue and to instead check after extraction (<code>''u'' ← ''Q''.extract_min()</code>) that it isn't revisiting, or that no shorter connection was found yet in the <code>if alt < dist[v]</code> block. This can be done by additionally extracting the associated priority <code>''p''</code> from the queue and only processing further <code>'''if''' ''p'' == dist[''u'']</code> inside the <code>'''while''' ''Q'' is not empty</code> loop.<ref name="Note2">Observe that {{mono|''p'' < dist[''u'']}} cannot ever hold because of the update {{mono|dist[''v''] ← ''alt''}} when updating the queue. See https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key for discussion.</ref>

These alternatives can use entirely array-based priority queues without decrease-key functionality, which have been found to achieve even faster computing times in practice. However, the difference in performance was found to be narrower for denser graphs.<ref name="chen_072">{{cite book |last1=Chen |first1=M. |url=http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf |title=Priority Queues and Dijkstra's Algorithm – UTCS Technical Report TR-07-54 – 12 October 2007 |last2=Chowdhury |first2=R. A. |last3=Ramachandran |first3=V. |last4=Roche |first4=D. L. |last5=Tong |first5=L. |publisher=The University of Texas at Austin, Department of Computer Sciences |year=2007 |location=Austin, Texas |ref=chen}}</ref>