大家好,又见面了,我是你们的朋友全栈君。
图论的基础知识不再阐述。 最短路径算法主要有二
Dijkstra算法研究的是从初始点到其他每一结点的最短路径 而Floyd算法研究的是任意两结点之间的最短路径
红字为各结点的编号,蓝字为各结点之间的距离
在与v1连通的点中,即在矩阵m的第1行,寻找最小值,最小值所在列即确定的最短路径的结点,如同v2最短,pb(2)=1,d(2)=1,对于已找到最短路径的v2上一结点为v1,path(2)=1;
接着,在
以上两种中寻找最短距离,最短为v6,pb(6)=1;d(6)=2;path(6)=1;
重复以上步骤,在
我们可以发现,所要寻找的最短路径即为 对于已找到最短路径的点(包括初始结点),在与其连通的,未找到最短路径的结点中,将之间距离与圆圈中的距离(即上一结点已找到的最短路径)相加,求得的最小值。 如果有多个相同的最短距离,任取其中一个。 最终最短路径即距离如下图
附上代码:
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
路径只需向上回溯就可得到。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/137532.html原文链接:https://javaforall.cn