Dijkstra算法，最短路径路由算法matlab代码

Dijkstra算法是一种最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率较低。

算法详细解释各网站都有，不太难。下边是对下图从D开始到A节点寻找最短路径的matlab代码，个人原创。

1.  
   %% Dijkstra算法
2.  
   %by Jubobolv369 at 2022/1/22
3.  
   clc;
4.  
   clear;
5.  
   close all;
6.  
    
7.  
   %% 初始化带权邻接矩阵,起点、终点等
8.  
   initRoute=[0 12 inf inf inf 16 14;
9.  
   12 0 10 inf inf 7 inf;
10.  
    inf 10 0 3 5 6 inf;
11.  
    inf inf 3 0 4 inf inf;
12.  
    inf inf 5 4 0 2 8;
13.  
    16 7 6 inf 2 0 9;
14.  
    14 inf inf inf 8 9 0;];
15.  
    [row,column]=size(initRoute);
16.  
    start_node=4;
17.  
    end_node=1;
18.  
    close_list=[];
19.  
    open_list=[];
20.  
    %closelist中加入初始节点
21.  
    close_list=[start_node,start_node,0];
22.  
    %% 如果closelist中没有终点，则遍历节点，通过比较逐渐加入节点到closelist。
23.  
    while isempty(find(close_list(:,1) == end_node))
24.  
    [last1,~]=size(close_list);%获取closelist的最后一行的索引
25.  
    now_node=close_list(last1,1);%当前节点编号
26.  
    now_length=close_list(last1,3);%当前最优长度
27.  
    [last2,~]=size(open_list); %%获取openlist的最后一行的索引
28.  
    now_list=initRoute(now_node,:); %从原始矩阵中取初当前节点的边权值
29.  
    i=1;
30.  
    %% 更新openlist
31.  
    for j=1:column
32.  
    %如果第j个节点可达、不是自身且不在close_list中，该点可能需要改动或添加到openlist中
33.  
    if now_list(j)~=inf && now_list(j)~=0 && isempty(find(close_list(:,1) == j))
34.  
    if last1==1
35.  
    open_list(i,1)=j;
36.  
    open_list(i,2)=now_node;
37.  
    open_list(i,3)=now_list(j);
38.  
    i=i 1;
39.  
    %如果不在openlist中，就将其添加到其中,否则将通过当前父节点到此节点的权值与之前的作比较
40.  
    else
41.  
    k=find(open_list(:,1) == j);
42.  
    if isempty(k)
43.  
    open_list(last2 i,1)=j;
44.  
    open_list(last2 i,2)=now_node;
45.  
    open_list(last2 i,3)=now_list(j) now_length;
46.  
    i=i 1;
47.  
    elseif open_list(k,3)>(now_list(j) now_length) %若現在的路徑長度小，則更新路徑
48.  
    open_list(k,1)=j;
49.  
    open_list(k,2)=now_node;
50.  
    open_list(k,3)=now_list(j) now_length;
51.  
    end
52.  
    end
53.  
    end
54.  
    end
55.  
    %% 更新closelist和openlist。将openlist里路径最小值的行放入closelist中
56.  
    [min_value,index]=min(open_list(:,3));
57.  
    close_list=[close_list; open_list(index,:)];
58.  
    open_list(index,:)=[];
59.  
    end
60.  
    %% 反找出最优路径及路径长度
61.  
    path_op=[end_node];
62.  
    index=find(close_list(:,1) == end_node);
63.  
    path_length=close_list(index,3)
64.  
    while isempty(find(path_op==start_node))
65.  
    path_op=[path_op close_list(index,2)];
66.  
    index=find(close_list(:,1) == close_list(index,2))
67.  
    end
68.  
    path_op
69.  
     
70.  
     

这篇好文章是转载于：学新通技术网