Editing Dijkstra's algorithm (section)

==Pseudocode==
In the following [[pseudocode]], {{mono|dist}} is an array that contains the current distances from the {{mono|<var>source</var>}} to other vertices, i.e. {{mono|dist[<var>u</var>]}} is the current distance from the source to the vertex {{mono|<var>u</var>}}. The {{mono|prev}} array contains pointers to previous-hop nodes on the shortest path from source to the given vertex (equivalently, it is the ''next-hop'' on the path ''from'' the given vertex ''to'' the source). The code {{mono|u ← vertex in ''Q'' with min dist[u]}}, searches for the vertex {{mono|<var>u</var>}} in the vertex set {{mono|<var>Q</var>}} that has the least {{mono|dist[<var>u</var>]}} value. {{mono|Graph.Edges(<var>u</var>, <var>v</var>)}} returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes {{mono|<var>u</var>}} and {{mono|<var>v</var>}}. The variable {{mono|<var>alt</var>}} on line 14 is the length of the path from the {{mono|<var>source</var>}} node to the neighbor node {{mono|<var>v</var>}} if it were to go through {{mono|<var>u</var>}}. If this path is shorter than the current shortest path recorded for {{mono|<var>v</var>}}, then the distance of {{mono|<var>v</var>}} is updated to {{mono|<var>alt</var>}}.<ref name=" mehlhorn" />
[[File:DijkstraDemo.gif|thumb|A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting ''u'' and prev[''u'']. Blue lines indicate where relaxing happens, i.e., connecting ''v'' with a node ''u'' in ''Q'', which gives a shorter path from the source to ''v''.]]

  1  '''function''' Dijkstra(''Graph'', ''source''):
  2     
  3      '''for each''' vertex ''v'' in ''Graph.Vertices'':
  4          dist[''v''] ← INFINITY
  5          prev[''v''] ← UNDEFINED
  6          add ''v'' to ''Q''
  7      dist[''source''] ← 0
  8     
  9      '''while''' ''Q'' is not empty:
 10          ''u'' ← vertex in ''Q'' with minimum dist[u]
 11          Q.remove(u)
 12         
 13          '''for each''' arc (u, v) in ''Q'':
 14              ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
 15              '''if''' ''alt'' < dist[''v'']:
 16                  dist[''v''] ← ''alt''
 17                  prev[''v''] ← ''u''
 18
 19      '''return''' dist[], prev[]

To find the shortest path between vertices {{mono|<var>source</var>}} and {{mono|<var>target</var>}}, the search terminates after line 10 if {{mono|<var>u</var> {{=}} <var>target</var>}}. The shortest path from {{mono|<var>source</var>}} to {{mono|<var>target</var>}} can be obtained by reverse iteration:

 1  ''S'' ← empty sequence
 2  ''u'' ← ''target''
 3  '''if''' prev[''u''] is defined '''or''' ''u'' = ''source'':          ''// Proceed if the vertex is reachable''
 4      '''while''' ''u'' is defined:                       ''// Construct the shortest path with a stack S''
 5          S.push(u)                             ''// Push the vertex onto the stack''
 6          ''u'' ← prev[''u'']                           ''// Traverse from target to source''

Now sequence {{mono|<var>S</var>}} is the list of vertices constituting one of the shortest paths from {{mono|<var>source</var>}} to {{mono|<var>target</var>}}, or the empty sequence if no path exists.

A more general problem is to find all the shortest paths between {{mono|<var>source</var>}} and {{mono|<var>target</var>}} (there might be several of the same length). Then instead of storing only a single node in each entry of {{mono|prev[]}} all nodes satisfying the relaxation condition can be stored. For example, if both {{mono|<var>r</var>}} and {{mono|<var>source</var>}} connect to {{mono|<var>target</var>}} and they lie on different shortest paths through {{mono|<var>target</var>}} (because the edge cost is the same in both cases), then both {{mono|<var>r</var>}} and {{mono|<var>source</var>}} are added to {{mono|prev[<var>target</var>]}}. When the algorithm completes, {{mono|prev[]}} data structure describes a graph that is a subset of the original graph with some edges removed. Its key property is that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph is the shortest path between those nodes graph, and all paths of that length from the original graph are present in the new graph. Then to actually find all these shortest paths between two given nodes, a path finding algorithm on the new graph, such as [[depth-first search]] would work.

===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>