Editing Dijkstra's algorithm (section)

== Description ==
{{Hatnote|Note: For ease of understanding, this discussion uses the terms intersection, road and map – however, in formal terminology these terms are vertex, edge and graph, respectively.}}
The shortest path between two [[Intersection (road)|intersections]] on a city map can be found by this algorithm using pencil and paper. Every intersection is listed on a separate line: one is the starting point and is labeled (given a distance of) 0. Every other intersection is initially labeled with a distance of infinity. This is done to note that no path to these intersections has yet been established. At each iteration one intersection becomes the current intersection. For the first iteration, this is the starting point.

From the current intersection, the distance to every [[Neighbourhood (graph theory)|neighbor]] (directly-connected) intersection is assessed by summing the label (value) of the current intersection and the distance to the neighbor and then [[Graph labeling|relabeling]] the neighbor with the lesser of that sum and the neighbor's existing label. I.e., the neighbor is relabeled if the path to it through the current intersection is shorter than previously assessed paths. If so, mark the road to the neighbor with an arrow pointing to it, and erase any other arrow that points to it. After the distances to each of the current intersection's neighbors have been assessed, the current intersection is marked as visited. The unvisited intersection with the smallest label becomes the current intersection and the process repeats until all nodes with labels less than the destination's label have been visited.

Once no unvisited nodes remain with a label smaller than the destination's label, the remaining arrows show the shortest path.