Dijkstra Algorithm,ChinesetranslateFor Digestra algorithm, it is poweredDirected graphG = (V, W) (V is a set of nodes, W is a set of edge weights. In the set W, the distance between nodes that are not directly connected is marked as infinity) Find the distance between a certain node and the other nodes.Shortest pathclassic algorithm. The core idea of this algorithm is to divide all nodes in the graph into 2 sets. Set S contains the nodes whose shortest path has been found, and Set U contains the distance of the node whose shortest path has not been found (the initial values are all set to infinity). Starting from a certain point v, the breadth priority traversal idea is used to traverse the graph. Every time a node is found, the node is removed from the set U and added to the set S, until U becomes an empty set, S contains the minimum distance from all nodes in the graph to the starting point. During the joining process, the shortest path length from source point v to each vertex in S is always maintained not greater than the shortest path length from source point v to any vertex in U.
The process of Dijkstra algorithm:
Select a certain node v as the starting point, and the distance from the starting point to the starting point is 0, that is, find the smallest path. This starting point is removed from the set U and added to the set S.
In the set W, view the distance between the starting point v and the nodes in the set U. Find the node k with the smallest distance (the shortest path to k is found), remove k from set U and add it to set S.
Taking k as the intermediate point, check the distance from k to node m in U in W. If the value of m in W is less than the value of m in U (k and m are directly connected), add the value of m in W and the value of k in U (from v to m from the distance from k to m), and then compare the addition result with the value of v to m in W (v does not pass the distance from the intermediate point to m), and select the smaller value and the data of new k in U.
Find the node n with the smallest value in U, which is the shortest path from v to n. Remove n from set U and add to set S. Repeat steps 3 and 4 with n as the intermediate point until all nodes in U move into S.
Figure 1
Manual calculation method of Dijkstra algorithm
As shown in Figure 1, start from node A. First we create a table and use it to record the value of each operation. This table header represents the nodes contained in the set U (the shortest path nodes are not found: A, B, C, D). The second line initializes the distances of each node to infinity and is represented by INF.
A
B
C
D
INF
INF
INF
INF
Point A is the starting point, the path from itself to itself is the shortest, which is 0, that is, the shortest path from A to A is found. Enter 0 in the second row of column A and underline it to indicate that A is removed from U. Write A on the leftmost left of the second row of the table, indicating that A is added to the set S.
A
B
C
D
A
0
INF
INF
INF
Create row 3 of the table. At this time, the set U contains {B, C, D}. From the figure, we can see that the distance between A->B is 1 (query set W), update the value of column B, and write it to the third row. From the figure, we can see that the distance between A->C is 5, and the value of column B is updated and written to the third row. From the figure, we can see that A->D cannot be directly reached and is marked as INF. In the third row of the table, find the minimum value of the elements {1, 5, INF} owned in the set U to obtain B. At this time, the data in the third row of column B is the minimum path of A->B. Underline the data in the third row of column B, and remove B from set U. At the same time, write B on the leftmost end of line 3, that is, add B to the set S.
A
B
C
D
A
0
INF
INF
INF
B
0
1
5
INF
Create row 4 of the table. At this time, the set U contains {C, D}, and Node B is the intermediate point. From the figure, we can see that the distance of B->C is 1, and the distance of A->B is stored in the column B of the table, which is 1, so the distance of A->B->C is 1+1=2. From the data in the third row of column C, it can be seen that the current distance to C is 5 (A directly reaches C). Find the minimum value of the two paths min(5,1+1)=2; update the C column data and write 2 to the 4th row of column C. From the figure, we can see that the distance between point B->D is 1, so the distance between point A->B->D is 1+1=2, and A->D cannot be directly reached, so the value is infinite INF (this value is recorded in set W, and at this time the value is equal to column D data in the table). Find the minimum value of the two paths min(INF, 1+1)=2. To update row column D data, write 2 to row D in column D. Take the minimum value of the data in the set U. Both C and D are 2. Choose one, and the shortest distance from the node to A is calculated. For example, choose C. Mark C.
A
B
C
D
A
0
INF
INF
INF
B
0
1
5
INF
C
0
1
2
2
Repeat the above operation to create row 5 of the table. At this time, only {D} is included in the set U, and node C is the intermediate point. From the figure, we can see that the distance between C->D is 1. The shortest distance of A->C has been found, and in the 4th row of column C in the above table, it is 2 (passing Node B). Therefore, the distance between A->B->C->D is 2+1=3. The minimum path to point D in the fourth row of column D in the table is 2 (passing point B). Find the minimum value of the two paths min(2,2+1)=2. That is, the minimum path of point D is 2, write 2 to the fifth row of column D and mark the fifth row of column D. At this time, set U is an empty set, and the elements in set S are {A, B, C, D}, and the calculation is completed. The data recorded in row 5 in the table is the minimum path value from point A to each point.
A
B
C
D
A
0
INF
INF
INF
B
0
1
5
INF
C
0
1
2
2
D
0
1
2
2
The specific path (passed node) can be found through the backtracking method. Find the column where the required point is located in the last table, and trace back from bottom to top. When the value changes, jump to the column where the elements in the S set corresponding to the row are located, record the point, and then continue to trace back until the starting point is reached.
If you find the specific path to point C, you can trace upward from the fifth row of column C, and the value changes when you reach the third row. The third row corresponds to B in the set S, then trace upward from the third row of column B, and reach the second row of column B, and the value changes. The element in the set S corresponding to the second row is A, which is the starting point and the backtracking is completed. The specific path is A->B->C.
C# corresponding to this ideasource codePlease refer to the article "Dijkstra Algorithm C# Demonstration Program".