Content deleted Content added
→Specialized variants: Update the complexity of Van Emde Boas tree to match the formula in the linked source |
m →Algorithm: Typo correction |
||
Line 25:
# 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
# Once the loop exits (steps 3–5), every visited node contains its shortest distance from the starting node.
| |||