1. Introduction to the algorithm
Dijkstra's algorithm was proposed by Dutch computer scientist Dijkstra in 1959. It is the shortest path algorithm from one node to traverse other nodes, and it solves the shortest path problem in the weighted graph.
2. Algorithmic thinking
1. Let G=(V, E) be a weighted directed graph, divide the node set V in the graph into two groups, the first group is the node set for which the shortest path has been obtained (represented by S, initially there are only A source point, each time a shortest path is obtained in the future, the node is added to the set S, until all nodes are added to S, the algorithm is over); Set (represented by U), the nodes of the second group are added to S in order of increasing shortest path length. In the process of joining, the length of the shortest path from the source point v to each node in S is always kept no greater than the length of the shortest path from the source point v to any node in U.
3. In addition, each node corresponds to a distance. The distance of the node in S is the shortest path length from v to this node, and the distance of the node in U is from v to this node. Only the nodes in S are intermediate nodes. The current shortest path length of .
3. Algorithm operation process
3.1 Preparation process
This algorithm uses a one-way weighted graph, which can find the adjacent node table of each node. Because it is more convenient to traverse with numbers in matlab, the letter nodes of A-G are changed to 1-7 number nodes.
3.2 Algorithm initialization
1. Initially, S only contains the starting point s; U contains other nodes except s, and the distance of the nodes in U is "the distance from the starting point s to the node" [for example, the distance of the node v in U is (s,v ), then s and v are not adjacent, then the distance of v is ∞].
2. Select "node k with the shortest distance" from U, and add node k to S; at the same time, remove node k from U.
3. Update the distance from each node in U to the starting point s. The reason why the distance of the nodes in U is updated is because k is determined in the previous step to be the node that finds the shortest path, so that k can be used to update the distances of other nodes; for example, the distance of (s,v) may be greater than (s,v) k)+(k,v) distance. Repeat steps (2) and (3) until all nodes are traversed.
3.3 Algorithm process
1. If the starting point is D and the end point is A, select node D, S={D(0)} U={A(∞), B(∞), C(3),E(4),F(∞) ,G(∞)}
2. Select node C according to U of the previous round, S={D(0),C(3)}
D passes through C to B: the shortest is DC+CB=10+3=13, which is less than the infinity of point B in the first step, so it needs to be updated
D passes through C to E: the shortest is DC+CE=3+5=8, which is greater than 4 at point E in the first step, so there is no need to update
D passes through C to F: the shortest is DC+CF=3+6=9, which is less than the infinity of point F in the first step, so it needs to be updated
U={A(∞),B(13),E(4),F(9),G(∞)}
3. Select node E according to U of the previous round, S={D(0),C(3),E(4)}
D goes through E to B: not adjacent to point E, so no update needed
D goes through E to F: the shortest is DE+EF=4+2=6, which is less than 9 of F in the second step, so it needs to be updated
D goes through E to G: the shortest is DE+DG=4+8=12 is less than the infinity of G in the second step, so it needs to be updated
U={A(∞),B(13),F(6),G(12)}
4. Select node F according to U of the previous round, S={D(0),C(3),E(4),F(6)}
D passes through F to A: the shortest is DE+DF+FA=4+2+16=22, which is less than the infinity of A in the third step, so it needs to be updated
D passes through F to B: the shortest is DE+EF+FB=4+2+7=13, which is equal to 13 of the third step B, so no update is required
D passes through F to G: the shortest is DE+EF+FG=4+2+9=15, which is greater than 12 of G in the third step, so there is no need to update
U={A(22),B(13),G(12)}
5. Select node G according to U of the previous round, S={D(0),C(3),E(4),F(6),G(12)}
D goes through G to A: the shortest is DE+EG+GA=4+8+14=26, which is greater than 22 of A in the fourth step, so no update is required
U={A(22),B(13)}
6. Select node B according to the U of the previous round, S={D(0),C(3),E(4),F(6),G(12),B(13)}
D goes through B to A: DC+CB+BA=3+10+12=25 is greater than 22 of A in the fifth step, so there is no need to update
U={A(22)}
7. Put A into S, S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)} U={ Ø}
8. That is, the optimal path from D to A is D→E→F→A, and the shortest distance is 22.
% Dijkstra algorithm
% author: Ally
% Date: 2020/12/18
clc
clear
close all
%% Diagram Definition
% According to the adjacent node table of the node and the letter node-Numeric node correspondence table, construct node cell array
nodes_dist = cell(0);
nodes_dist(1,:) = {1, [2, 6, 7], [12, 16, 14]};
nodes_dist(2,:) = {2, [1, 3, 6], [12, 10, 7]};
nodes_dist(3,:) = {3, [2, 4, 5, 6], [10, 3, 5, 6]};
nodes_dist(4,:) = {4, [3, 5], [3, 4]};
nodes_dist(5,:) = {5, [3, 4, 6, 7], [5, 4, 2, 8]};
nodes_dist(6,:) = {6, [1, 2, 3, 5, 7], [16, 7, 6, 2, 9]};
nodes_dist(7,:) = {7, [1, 5, 6], [14, 8, 9]};
%% Algorithm initialization
% S/U The first column of the represents the node number
% for S，The second column represents the minimum distance obtained from the source node to this node, and will not be changed;
% for U，The second column represents the minimum distance temporarily obtained from the source node to this node, which may change
S = [4, 0];
U(:,1) = [1, 2, 3, 5, 6, 7];
U(:,2) = [inf, inf, 3, 4, inf, inf];
% Initialization of optimal path and temporary optimal path
path_opt = cell(7,2);
path_opt(4,:) = {4, 4};
path_temp = cell(7,2);
path_temp(3,:) = {3, [4, 3]};
path_temp(4,:) = {4, 4};
path_temp(5,:) = {5, [4, 5]};
%% loop through all nodes
while ~isempty(U)
% exist U Set to find the current minimum distance value and the corresponding node,and remove the node to S in the collection
[dist_min, idx] = min(U(:,2));
node_min = U(idx, 1);
S(end+1,:) = [node_min, dist_min];
U(idx,:) = [];
% Add the node with the smallest distance value to the optimal path set
path_opt(node_min,:) = path_temp(node_min,:);
%% Traverse the neighbor nodes of the minimum distance node in turn to determine whether it is in the U Update the distance value of neighbor nodes in the set
for i = 1:length(nodes_dist{node_min, 2})
% Nodes that need to be judged
node_temp = nodes_dist{node_min, 2}(i);
% find out U Node in the collection node_temp the index value of
idx_temp = find(node_temp == U(:,1));
% Determine whether to update
if ~isempty(idx_temp)
if dist_min + nodes_dist{node_min, 3}(i) < U(idx_temp, 2)
U(idx_temp, 2) = dist_min + nodes_dist{node_min, 3}(i);
% Update the temporary optimal path
path_temp{node_temp, 1} = node_temp;
path_temp{node_temp, 2} = [path_opt{node_min, 2}, node_temp];
end
end
end
end
Learning from station B: Xiaoli's Ally
Video link: Path Planning and Trajectory Tracking Series Algorithm Learning_Lesson 1_Dijkstra's Algorithm