一 实现原理

Dijkstra算法研究的是从初始点到其他每一结点的最短路径 

以下图为例，首先介绍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(n);%定义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;
route=zeros(n);                         %用于存放每一点的路径；每一行代表一条路径
for i=1:n                               %%设置矩阵中非零非无穷的值for j=1:nif(m(i,j)==0)m(i,j)=inf;endend
end
%设置矩阵对角线上的值为0
for i=1:nm(i,i)=0;
endpb(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(plus<min)min=plus;lastpoint=fb(i);newpoint=tb(j);endendendd(newpoint)=min;pb(newpoint)=1;path(newpoint)=lastpoint;      %最小值时的与之连接点%回溯函数，每一行显示从终点到起点的路径for i=1:nroute(i,1)=i;              %先将每一个起点（route的第一列）初始化为每条路径的终点for j=2:nx=route(i,j-1);if(x~=0)route(i,j)=path(x);elsecontinue;endendend
end

三 算法结果

1. 在path中保存的是：各点最短路径的上一点标号：如path(2)=1：表示v2的上一节点为v1；path(5)=6：表示v5的上一节点为v6；这与我们分析一致；

2. route数组中存放的是每一个节点的最短路径，（此处由终及始，需要由始及终将route每一列颠倒即可）。

以route的第四行为例，path(4)=3：表示v4的上一个节点为v3；path（3）=6：表示V3的上一个节点是6；再path(6)=1：表示v6的上一个节点为1，至此，终点为v4的链路已经清晰，即v4-v3-v6-v1；这也与我们分析一致。