求邻接矩阵任意两点间的最短距离。matlab。程序在下面有没有哪位大神能给解释一下后边的是什么意思 50

求邻接矩阵任意两点间的最短距离。matlab。程序在下面有没有哪位大神能给解释一下后边的是什么意思%Dijkstra最短路算法Matlab程序,用于求从各点之间的最短路距... 求邻接矩阵任意两点间的最短距离。matlab。程序在下面有没有哪位大神能给解释一下后边的是什么意思%Dijkstra最短路算法Matlab程序,用于求从各点之间的最短路距离
%D为邻接矩阵需要输入
%d为s到其它各点最短距离
%pre记载了最短路径生成路线
clear all
clc
D=[0 6 inf inf 5 6 inf 5 inf
6 0 9 inf inf 9 inf 3 inf
inf 9 0 7 inf inf 4 inf inf
inf inf 7 0 6 4 6 inf 3
5 inf inf 6 0 5 inf inf 4
6 9 inf 4 5 0 5 inf inf
inf inf 4 6 inf 5 0 inf inf
5 3 inf inf inf inf inf 0 inf
inf inf inf 3 4 inf inf inf 0];%这是邻接矩阵
[m,n]=size(D);%m行n列,这里m=n=9
E=zeros(m,n);%E为任意两点间最短距离矩阵
for s=1:m
%当s=1时,就是求1这个点到其他各个点的最短距离,同理,当s=2时,……=9时。
d=inf.*ones(1,m);%初始化
d(1,s)=0;%s点到s点的最短距离为0
ok=zeros(1,m);%初始化,用来记录已经求得最短路径的点
pre=zeros(1,m);%初始化
while length(find(ok==1))<m
minD=inf;
for k=1:m
if ok(k)==0&&minD>d(k)
minD=d(k);
y=k;
end
end
if minD==inf
break;
end
ok(y)=1;
for i=1:m
if D(y,i)~=inf
alt=d(y)+D(y,i);
if alt<d(i)
d(i)=alt;
pre(i)=y;
end
end
end
end
E(s,:)=d;
end
展开
 我来答 举报
活宝上大夫
2017-04-14 · TA获得超过7491个赞
知道大有可为答主
回答量:5601
采纳率:0%
帮助的人:1113万
展开全部
根据lz要求,最合适的是floyd算法

下面就是根据这个算法写的代码,lz可以自己改成函数

D=[0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0];

n=length(D);

for k=1:n
for i=1:n
for j=1:n
if 0<D(i,k) & 0<D(k,j)
if D(i,j)==0 & i~=j
D(i,j)=D(i,k)+D(k,j);
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j));
end
end
end
end
end

答案就储存在D矩阵当中,这里
D =
0 1 2 1 2 3
1 0 1 2 2 2
2 1 0 1 1 1
1 2 1 0 1 2
2 2 1 1 0 1
3 2 1 2 1 0

算法为O(n3)的,256^3=2^24 大概等于1600万

效率上完全能够忍受。
宁静又妥善灬萨摩耶K
2017-04-14 · TA获得超过2275个赞
知道小有建树答主
回答量:1万
采纳率:0%
帮助的人:1241万
展开全部
用floyd算法也可以,另外一个取巧的方法是把plus重载成min,mtimes重载成plus,然后直接把邻接矩阵求N次方(N是结点个数)就行了
追问
我不懂什么算法,只知道这个现成的可以算出来,可我又看不懂啥意思
能给解释下后半部分吗
抢首赞 已赞过 已踩过<
你对这个回答的评价是?
评论 举报 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式