There are many algorithms for calculating the shortest distance between two nodes in the graph. The most famous algorithm is the Dijkstra algorithm proposed by Dijkstra in 1959. The algorithm requires each node to be marked with the distance from the source node to the node along the known best path. Since a path is not known at the beginning, all nodes are marked with infinity. As the algorithm progresses and the path is continuously found, the label changes accordingly to reflect a better path. An annotation can be temporary (changeable). All annotations are temporary initially, but once it is found that the annotation represents the shortest possible path from the source node to the node, it becomes permanent and no longer Make changes.
To illustrate how the labeling algorithm works, please refer to the figure on the right, where the number indicates the distance between two nodes. To find the shortest distance from A to D, first mark A as permanent (indicated by a solid circle) as the start, then examine each node adjacent to A in turn, and relabel these points with their respective distances to A. After finding node B as the shortest path node, make it a permanent node. Next, starting from node B, check all nodes adjacent to B. If the sum of the label of B and the distance from B to all nodes is less than the label of this node, then Relabel this node.
