Editing Dijkstra's algorithm (section)

== Algorithm ==
[[File:Dijkstras_progress_animation.gif|thumb|Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a target node (upper right, green) in a [[Robotics|robot]] [[motion planning]] problem. Open nodes represent the "tentative" set (aka set of "unvisited" nodes). Filled nodes are the visited ones, with color representing the distance: the redder, the closer (to the start node). Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular [[wavefront]] as Dijkstra's algorithm uses a [[Consistent heuristic|heuristic]] of picking the shortest known path so far.]]
The algorithm requires a starting node, and computes the shortest distance from that starting node to each other node. Dijkstra's algorithm starts with infinite distances and tries to improve them step by step:

# Create a [[Set (abstract data type)|set]] of all unvisited nodes: the unvisited set.
# Assign to every node a distance from start value: for the starting node, it is zero, and for all other nodes, it is infinity, since initially no path is known to these nodes. During execution, the distance of a node ''N'' is the length of the shortest path discovered so far between the starting node and ''N''.<ref>{{Cite encyclopedia |encyclopedia=Encyclopedia of Operations Research and Management Science |publisher=Springer |date=2013 |editor1-last=Gass |editor1-first=Saul I |volume=1 |doi=10.1007/978-1-4419-1153-7 |isbn=978-1-4419-1137-7 |last2=Fu |first2=Michael |last1=Gass |first1=Saul |chapter=Dijkstra's Algorithm |editor2-first=Michael C |editor2-last=Fu |via=Springer Link |doi-access=free}}</ref>
# From the unvisited set, select the current node to be the one with the smallest (finite) distance; initially, this is the starting node (distance zero). If the unvisited set is empty, or contains only nodes with infinite distance (which are unreachable), then the algorithm terminates by skipping to step 6. If the only concern is the path to a target node, the algorithm terminates once the current node is the target node. Otherwise, the algorithm continues.
# For the current node, consider all of its unvisited neighbors and update their distances through the current node; compare the newly calculated distance to the one currently assigned to the neighbor and assign the smaller one to it. For example, if the current node ''A'' is marked with a distance of 6, and the edge connecting it with its neighbor ''B'' has length 2, then the distance to ''B'' through ''A'' is 6 + 2 = 8. If B was previously marked with a distance greater than 8, then update it to 8 (the path to B through A is shorter). Otherwise, keep its current distance (the path to B through A is not the shortest).
# After considering all of the current node's unvisited neighbors, the current node is removed from the unvisited set. Thus a visited node is never rechecked, which is correct because the distance recorded on the current node is minimal (as ensured in step 3), and thus final. Repeat from step 3.
# Once the loop exits (steps 3–5), every visited node contains its shortest distance from the starting node.