dijkstra算法
图论的基础知识不再阐述。
- 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路径只需向上回溯就可得到。
相关阅读
本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，弗洛伊德算法，迪杰斯特拉算法，Bellman-Ford算法1），深度或广度优先搜索
前言 SPFA" role="presentation">SPFASPFA算法由于它上限 O(NM)=O(VE)" role="presentation">O(NM)=O(VE)O(NM)=O(VE)的时间复
迪杰斯特拉算法可以用来求图的最短路径，本文通过对一个无向图最短路径的求取问题来讲解迪杰斯特拉算法。假如有无向图如下： 首先我