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

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

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

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

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

*
首先定义几个变量

结点个数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存放这一条最短路径的前一个结点，通过对每一点的回溯，可以找到最短路径。

*
根据距离写出以下距离矩阵

*
确定初始点为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
路径只需向上回溯就可得到。

热门工具换一换