1. 按

Dijkstra算法用于求解一个顶点到另一顶点的最短路径，它采用了非暴力的贪心思想，因此时间复杂度较低，为O(N^2)。
Dijkstra算法是一种贪心算法，每一次都求最短路径，但与常见的贪心算法不同的是，Dijkstra算法是一种步步为营的贪心算法，因此能求解一个顶点到另一个顶点的最短路径。

2. 算法讲解

2.1. 理论讲解

1. 约定AimedPathNodes为所要求解的从某一目标点HeadNode（为了便于理解，将此节点约定为HeadNode，即头结点，目标路径上开头的那个节点）到另一目标点TrailNode（为了便于理解，将此节点约定为TrailNode，即尾结点，目标路径上结尾的那个节点）的最短的目标路径。
2. 目标路径是由多个点组成的，刚开始时目标路径AimedPathNodes仅包含起始点HeadNode。
3. 找出当前目标路径（AimedPathNodes）的最近的邻接点并将其加入到AimedPathNodes中，随后再次找出AimedPathNodes的最近邻接点，并将其加入到AimedPathNodes中，这样一直下去，直到AimedPathNodes包含结尾的那个点（TrailNode）为止。

2.2. 实例讲解

2.2.1. 初始化

给每个点进行编号v1、v2 … v11，这里的v是vertex的缩写，是点的意思，因此v1是点1的意思。
给每条边初始化一个权重，权重用数字表示，如下图中v1与v2两点间的边的权重为2。
此例用于求解v1到v11两点间的最短路径。
约定AimedPathNodes为一个存储目标路径上所有点的变量。

2.2.2. 执行算法

1. 刚开始时AimedPathNodes仅包含v1
   
2. 此时AimedPathNodes为v1。
   找AimedPathNodes最近的邻接点，即找v1的最近的邻接点。
   与v1相邻的点为v2、v3、v4，因此v1的邻接点为v2、v3、v4。
   其中v1与v2的边权重位2，v1与v3的边权重位8，v1与v4的边权重位1。
   易得：v1的最近邻接点为v4
   将v4加入到AimedPathNodes。
   
3. 此时AimedPathNodes为v1, v4。
   找AimedPathNodes的最近邻接点，即先找出v1的不包含AimedPathNodes上的点的最短邻接点v2，再找出v4的不包含AimedPathNodes上的点的最近邻接点v3。
   由于v1到v2的距离为2，v4到v3的距离为7，因此v2为到此时AimedPathNodes的最近点，将v2加入到AimedPathNodes。
   
4. 此时AimedPathNodes为v1, v4, v2。
   易得AimedPathNodes的最近邻接点为v5，将v5加入到AimedPathNodes中
   
5. 此时AimedPathNodes为v1, v4, v2, v5。
   易得AimedPathNodes的最近邻接点为v8
   
6. 此时AimedPathNodes为v1, v4, v2, v5, v8。
   AimedPathNodes的最近邻接点为v6
   
7. 此时AimedPathNodes为v1, v4, v2, v5, v8, v6。
   AimedPathNodes的最近邻接点为v3
   
8. 此时AimedPathNodes为v1, v4, v2, v5, v8, v6, v3。
   AimedPathNodes的最近邻接点为v7
   
9. 此时AimedPathNodes为v1, v4, v2, v5, v8, v6, v3, v7。
   AimedPathNodes的最近邻接点为v10
   
10. 此时AimedPathNodes为v1, v4, v2, v5, v8, v6, v3, v7, v10。
    AimedPathNodes的最近邻接点为v9
    
11. 此时AimedPathNodes为v1, v4, v2, v5, v8, v6, v3, v7, v10, v9。
    AimedPathNodes的最近邻接点为v11
    
12. 停止找最近的邻接点。实际求解最短路径时，除了上面的之外，还要再声明一个变量用于存储最短路径，并且每一步还有一个对该变量进行退栈和入栈的操作。
    

3. matlab实现

dijkstra.m

function [min,path]=dijkstra(w,start,terminal)
    n=size(w,1); label(start)=0; f(start)=start;
    for i=1:n
       if i~=start
           label(i)=inf;
    end, end
    s(1)=start; u=start;
    while length(s)<n
       for i=1:n
          ins=0;
          for j=1:length(s)
             if i==s(j)
                ins=1;
             end,  
          end
          if ins==0
             v=i;
             if label(v)>(label(u)+w(u,v))
                label(v)=(label(u)+w(u,v)); 
             f(v)=u;
             end, 
          end, 
       end   
    v1=0;
       k=inf;
       for i=1:n
             ins=0;
             for j=1:length(s)
                if i==s(j)
                   ins=1;
                end, 
             end
             if ins==0
                v=i;
                if k>label(v)
                   k=label(v);  v1=v;
                end,  
             end,  
       end
       s(length(s)+1)=v1;  
       u=v1;
    end
    min=label(terminal); path(1)=terminal;
    i=1; 
    while path(i)~=start
          path(i+1)=f(path(i));
          i=i+1 ;
    end
    path(i)=start;
    L=length(path);
    path=path(L:-1:1);

4. 测试

4.1. 测试一

• 代码

  weight=[0     2     8     1   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
       2     0     6   Inf     1   Inf   Inf   Inf   Inf   Inf   Inf;
       8     6     0     7     5     1     2   Inf   Inf   Inf   Inf;
       1   Inf     7     0   Inf   Inf     9   Inf   Inf   Inf   Inf;
     Inf     1     5   Inf     0     3   Inf     2     9   Inf   Inf;
     Inf   Inf     1   Inf     3     0     4   Inf     6   Inf   Inf;
     Inf   Inf     2     9   Inf     4     0   Inf     3     1   Inf;
     Inf   Inf   Inf   Inf     2   Inf   Inf     0     7   Inf     9;
     Inf   Inf   Inf   Inf     9     6     3     7     0     1     2;
     Inf   Inf   Inf   Inf   Inf   Inf     1   Inf     1     0     4;
     Inf   Inf   Inf   Inf   Inf   Inf   Inf     9     2     4     0;]
  [dis, path]=dijkstra(weight,1, 11)
  

• 图
  
• 结果
  dis = 13
  path = 1 2 5 6 3 7 10 9 11

4.2. 测试二

• 代码

  weight=[0     8   Inf   Inf   Inf   Inf     7     8   Inf   Inf   Inf;
     Inf     0     3   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
     Inf   Inf     0     5     6   Inf     5   Inf   Inf   Inf   Inf;
     Inf   Inf   Inf     0     1   Inf   Inf   Inf   Inf   Inf    12;
     Inf   Inf     6   Inf     0     2   Inf   Inf   Inf   Inf    10;
     Inf   Inf   Inf   Inf     2     0     9   Inf     3   Inf   Inf;
     Inf   Inf   Inf   Inf   Inf     9     0   Inf   Inf   Inf   Inf;
       8   Inf   Inf   Inf   Inf   Inf   Inf     0     9   Inf   Inf;
     Inf   Inf   Inf   Inf     7   Inf   Inf     9     0     2   Inf;
     Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf     2     0     2;
     Inf   Inf   Inf   Inf    10   Inf   Inf   Inf   Inf   Inf     0;];
  [dis, path]=dijkstra(weight,1, 11)
  

• 图
  
• 结果
  dis = 21
  path = 1 8 9 10 11

图论的基础知识不再阐述。
最短路径算法主要有二

1. Dijkstra算法
2. Floyd算法

Dijkstra算法研究的是从初始点到其他每一结点的最短路径
而Floyd算法研究的是任意两结点之间的最短路径

以下图为例，首先介绍Dijstra的原理

红字为各结点的编号，蓝字为各结点之间的距离

1. 首先定义几个变量

   结点个数n；
   二维矩阵M（nxn），距离矩阵，连通的结点间即为距离，不连通的结点间为正无穷，和自己的距离为0；
   一维矩阵pb（1xn），若第i点已找到最短路径，则fp（i）=1，否则等于0，对于初始结点，fp=1；
   距离矩阵d（1xn），若第i点已找到最短路径，则的d（i）=最短距离，否则为0，初始结点d=0；
   上一结点矩阵path（1xn)，若第i点找到了最短路径，则path存放这一条最短路径的前一个结点，通过对每一点的回溯，可以找到最短路径。

2. 根据距离写出以下距离矩阵

   

3. 确定初始点为v1，则pb(1)=1;

   在图中，结点上，我们将已找到最短路径的点标为它的最短距离，（可以理解为v1点已找到最短路径，距离为0），未找到的其余点表为正无穷（即表示不连通）。
   
   在与v1连通的点中，即在矩阵m的第1行，寻找最小值，最小值所在列即确定的最短路径的结点，如同v2最短，pb（2）=1，d（2）=1，对于已找到最短路径的v2上一结点为v1，path（2）=1；
   
   接着，在

   • 与v1连通的，且未找到最短距离的节点的距离
   • 与v2连通的，且未找到最短距离节点的距离+v2的最短距离

   以上两种中寻找最短距离，最短为v6，pb（6）=1；d（6）=2；path（6)=1;
   
   重复以上步骤，在

   • 与v1连通的，且未找到最短距离的节点的距离
   • 与v2连通的，且未找到最短距离节点的距离+v2的最短距离
   • 与v6连通的，且未找到最短距离节点的距离+v2的最短距离
     以上三种中寻找最短路径，最短为v3,pb(3)=1;d(3)=3);path(3)=6;
     
     我们可以发现，所要寻找的最短路径即为
     对于已找到最短路径的点（包括初始结点），在与其连通的，未找到最短路径的结点中，将之间距离与圆圈中的距离（即上一结点已找到的最短路径）相加，求得的最小值。
     如果有多个相同的最短距离，任取其中一个。
     最终最短路径即距离如下图
     

附上代码：

clc;clear;
n=6;   %设置矩阵大小
temp=1;  %设置起始点
m=zeros(6);%定义n阶零矩阵
m(1,2)=1;m(1,6)=2;%设置矩阵中非零非无穷的值
m(2,1)=1;m(2,3)=4;m(2,6)=4;
m(3,2)=4;m(3,4)=2;m(3,6)=1;
m(4,3)=2;m(4,5)=3;m(4,6)=3;
m(5,4)=3,m(5,6)=5;
m(6,1)=2;m(6,2)=4;m(6,3)=1;m(6,4)=3;m(6,5)=5;

for i=1:n
    for j=1:n
       if(m(i,j)==0)
           m(i,j)=inf;
       end
    end
end
for i=1:n
    m(i,i)=0;
end
pb(1:length(m))=0;pb(temp)=1;%求出最短路径的点为1，未求出的为0
d(1:length(m))=0;%存放各点的最短距离
path(1:length(m))=0;%存放各点最短路径的上一点标号
while sum(pb)<n %判断每一点是否都已找到最短路径
 tb=find(pb==0);%找到还未找到最短路径的点
 fb=find(pb);%找出已找到最短路径的点
 min=inf;
 for i=1:length(fb)
     for j=1:length(tb)
         plus=d(fb(i))+m(fb(i),tb(j));  %比较已确定的点与其相邻未确定点的距离
         if((d(fb(i))+m(fb(i),tb(j)))<min)
             min=d(fb(i))+m(fb(i),tb(j));
             lastpoint=fb(i);
             newpoint=tb(j);
         end
     end
 end
 d(newpoint)=min;
 pb(newpoint)=1;
 path(newpoint)=lastpoint; %最小值时的与之连接点
end
d
path

路径只需向上回溯就可得到。

 为了搞清楚最短路径的算法过程，自己编写代码实现dijkstra算法寻找路径

% 文件名：dijkstra.m
% 时间：2020年9月12日
% 来源：https://blog.csdn.net/lishan132/article/details/108527271
% 功能：利用dijkstra算法计算两点间的最短路径
% dist：起点与终点之间的最短距离值
% path：最短路径索引
% Distance：最短路径下的距离值
% A：邻接矩阵
% strat：起点编号
% dest：终点编号
function [dist,path,Distance] = dijkstra(A,start,dest)
% 测试数据 A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
% 测试数据 start = 1;
% 测试数据 dest = 4;
% 计算程序运行时间
tic  %开始计时

% 初始化操作
p = size(A,1);        %计算顶点数目 
S(1) = dest;          %初始化集合S，已加入到路径中的顶点编号
U = 1:p;              %初始化集合U，未加入到路径中的顶点编号
U(dest) = [];         %删除终点编号
Distance = zeros(2,p);  %初始化所有顶点到终点dest的距离
Distance(1,:) = 1:p;    %重赋值第一行为各顶点编号
Distance(2,1:p) = A(dest,1:p);  %重赋值第二行为邻接矩阵中各顶点到终点的距离
new_Distance = Distance;
D = Distance;            %初始化U中所有顶点到终点dest的距离
D(:,dest) = [];          %删除U中终点编号到终点编号的距离
path = zeros(2,p);  %初始化路径
path(1,:) = 1:p;    %重赋值第一行为各顶点编号
path(2,Distance(2,:)~=inf) = dest;  %距离值不为无穷大时，将两顶点相连

% 寻找最短路径
while ~isempty(U)  %判断U中元素是否为空
    index = find(D(2,:)==min(D(2,:)),1);  %剩余顶点中距离最小值的索引
    k = D(1,index);   %发现剩余顶点中距离终点最近的顶点编号
    
    %更新顶点
    S = [S,k];     %将顶点k添加到S中
    U(U==k) = [];  %从U中删除顶点k  
    
    %计算距离
    new_Distance(2,:) = A(k,1:p)+Distance(2,k); %计算先通过结点k，再从k到达终点的所有点距离值
    D = min(Distance,new_Distance);  %与原来的距离值比较，取最小值  
   
    %更新路径
    path(2,D(2,:)~=Distance(2,:)) = k;  %出现新的最小值，更改连接关系，连接到结点k上 
    
    %更新距离
    Distance = D;  %更新距离表为所有点到终点的最小值
    D(:,S) = [];   %删除已加入到S中的顶点
end
dist = Distance(2,start);  %取出指定起点到终点的距离值
toc %计时结束

% 输出结果
fprintf('找到的最短路径为：');
while start ~= dest    %到达终点时结束
    fprintf('%d-->',start);  %打印当前点编号
    next = path(2,start);    %与当前点相连的下一顶点
    start = next;            %更新当前点
end
fprintf('%d\n',dest);
fprintf('最短路径对应的距离为：%d\n',dist);
end

此函数共有3个输入参数，3个输出参数

输入参数说明

A：邻接矩阵，存储各顶点之间的距离值，是一个大小为顶点个数的方阵，对角线元素为0
strat：起点编号
dest：终点编号

输出参数说明

dist：指定起点与终点之间的最短距离值
path：最短路径索引，一共两行，第一行的值依次为各顶点编号，第二行的值为与第一行顶点相连的顶点编号
Distence：最短路径下的距离值，一共两行，第一行的值依次为各顶点编号，第二行的值为对应顶点到终点的最小距离值

算法有效性的测试如下：

 根据上图，想计算A点到D点的最短路径和距离，经过理论分析，其最短路径应为A-->F-->E-->D，最短距离为16+2+4=22

下面输入代码进行验证

输入代码

A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
start = 1;
dest = 4;
[dist,path,Distance] = dijkstra(A,start,dest)

时间已过 0.005424 秒。
找到的最短路径为：1-->6-->5-->4
最短路径对应的距离为：22

dist =

    22

path =

     1     2     3     4     5     6     7
     6     3     4     4     4     5     5

Distance =

     1     2     3     4     5     6     7
    22    13     3     0     4     6    12

 输入其他任意两个点，换一个距离矩阵，依然能正确输出最短路径和相应的距离值，算法的有效性得到验证

 输入以下代码可生成最终的最短路径图，输出结果与起点值无关，任意点到D点的最短路径均可从图中找到

A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
start = 1;
dest = 4;

[~,path,Distance] = dijkstra(A,start,dest)

path(:,dest) = [];
Distance(:,dest) = [];
s = path(1,:);
t = path(2,:);
weights = Distance(2,:);
names = {'A' 'B' 'C' 'D' 'E' 'F' 'G'};

g = digraph(s,t,weights,names);

plot(g,'EdgeLabel',g.Edges.Weight)

 可以看到，图中所有点均向D点聚集，且显示了每一个点到D点的最短距离

下面，使用matlab图论工具箱的函数寻找最短路径，再进行一个对比验证

图论工具箱中求最短路径的函数有以下3个，本文使用shortestpath，matlab命令窗口中输入doc shortestpath即可查看用法

shortestpath    两个单一节点之间的最短路径
shortestpathtree    从节点的最短路径树
distances    所有节点对组的最短路径距离

% 文件名：shortpath.m
% 时间：2020年9月12日
% 来源：https://blog.csdn.net/lishan132/article/details/108527271
% 功能：利用matlab自带的shortestpath函数计算两点间的最短路径
% dist：起点与终点之间的最短距离值
% path：最短路径
function [dist,path] = shortpath(A,start,dest)
%使用matlab自带的函数计算最短路径
tic
A(A==inf) = 0;  %将无穷大值变为0
[t,s,weights] = find(A);  %邻接矩阵中非零值的列、行号索引,及对应值
G = digraph(s,t,weights);  %生成一幅带权值的有向图
[path,dist] = shortestpath(G,start,dest);  %计算最短路径
toc

%展示结果
plot(G,'EdgeLabel',G.Edges.Weight)
fprintf('找到的最短路径为：');
fprintf('%d ',path);
fprintf('\n');
fprintf('最短路径对应的距离为：%d\n',dist);
end

 命令窗口输入以下代码验证结果

A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
start = 1;
dest = 4;
[dist,path] = shortpath(A,start,dest)

时间已过 0.002112 秒。
找到的最短路径为：1 6 5 4 
最短路径对应的距离为：22

dist =

    22

path =

     1     6     5     4

两者结果一致，再次验证算法的有效性，而且自己写的Dijkstra算法的代码还能够一次输出所有点到终点的距离及路径表

仅一次测试以及少量的数据规模N不足以说明算法的解决效率，为了对两个算法性能进行一个比较，特地写了一个测试程序，输入的数据规模N从10到2000变化，并注释dijkstra.m、shortpath.m两个文件中的计时和输出结果部分的代码，程序如下

% 文件名：compar1.m
% 时间：2020年9月12日
% 来源：https://blog.csdn.net/lishan132/article/details/108527271
% 功能：比较自己实现的dijkstra算法与matlab图论工具箱函数的效率性能
% 说明：请先将dijkstra.m、shortpath.m文件与本文件放在同一目录下
clear
close
clc
iter = 200;  %测试次数
t1 = zeros(1,iter);  %算法1时间
t2 = zeros(1,iter);  %算法2时间
for i = 1:iter
    %% 第一步：生成测试数据，距离矩阵A,起点start，终点dest
    clearvars -except iter i t1 t2 %清空除iter,i,t1,t2外的所有变量
    N = i*10;  %输入数据规模
    ub = 15;  %输入数据距离上限
    A = unifrnd (0, ub, N, N);  %生成一个服从均匀分布的矩阵，数值范围[0,ub]，矩阵大小n×n
    A = A - A';
    A(A<0) = inf;
    start = round(rand(1,1)*(N-1))+1;
    dest = round(rand(1,1)*(N-1))+1;
    while start == dest
        dest = round(rand(1,1)*(N-1))+1;
    end
    %% 第二步：计算自己编写的dk算法的运行时间
    tic  %开始计时
    dijkstra(A,start,dest);
    t1(i) = toc; %计时结束

    %% 第三步：计算使用matlab自带图论工具箱算法的运行时间
    tic  %开始计时
    shortpath(A,start,dest);
    t2(i) = toc;  %计时结束
end

%% 第四步：绘制算法所需时间图
plot(1:iter,t1);
hold on
plot(1:iter,t2);
legend("文中dijkstra算法","图论工具shortestpath函数")
title("算法耗费时间比较")

惊喜地发现，随着数据规模的增大，自己写的Dijkstra算法与图论工具函数shortestpath相比，耗时更低，而且差距越来越大。

当然，此处还是有些不严谨，因为我在使用图论工具函数shortestpath解决问题时，前面自己还写了三条参数的处理语句，这部分语句的处理过程也是算入时间的

结论

本文实现了dijkstra算法的Matlab代码，并封装成一个函数，给定一个邻接矩阵，以及指定一个终点，可以直接输出任意点到终点的最短路径和相应的距离值，相对matlab自带的图论工具箱函数，其运算速度快，输出数据全，方便二次开发，提高效率。但自己写的程序中每次只寻找一个新的结点加入，有多少个结点，while中的循环体就要执行多少次，每一次循环均要更新一次所有结点到终点的距离值，当结点数据非常大时，时间复杂度为O(N^2)，因此还有继续优化的空间，根据相关文献，可用堆进行优化，也可从能否一次加入多个新结点，而不是一个来考虑加快搜索速度。

参考文章：

[1] 数据结构--Dijkstra算法最清楚的讲解 https://blog.csdn.net/heroacool/article/details/51014824

[2] 通俗易懂理解——dijkstra算法求最短路径 https://zhuanlan.zhihu.com/p/40338107

[3] Dijkstra算法及其matlab实现 https://blog.csdn.net/u011317780/article/details/82429511

[4] 李建东，盛敏编著. 通信网络基础. 北京：高等教育出版社, 2004.08.

[5] 迪杰斯特拉 & 堆优化 https://blog.csdn.net/CSDNjiangshan/article/details/79345031