最短路径Dijkstra算法原理及Matlab实现

大家好，欢迎来到IT知识分享网。

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

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

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