作业帮matlab floyd 算法注释
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/11/09 03:43:45
matlab floyd 算法注释
function [D,R]=floyd(A)
%用floyd算法实现求任意两点之间的最短路程.可以有负权
%参数D为连通图的权矩阵
% A=[0 2 8 1 inf inf inf inf
% 2 0 6 inf 1 inf inf inf
% 8 6 0 7 5 1 2 inf
% 1 inf 7 0 inf inf 9 inf
% inf 1 5 inf 0 3 inf 8
% inf inf 1 inf 3 0 4 6
% inf inf 2 9 inf 4 0 3
% inf inf inf inf 8 6 3 0];
D=A;n=length(D);
for i=1:n
for j=1:n
R(i,j)=i;%赋路径初值
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)
function [D,R]=floyd(A)
%用floyd算法实现求任意两点之间的最短路程.可以有负权
%参数D为连通图的权矩阵
% A=[0 2 8 1 inf inf inf inf
% 2 0 6 inf 1 inf inf inf
% 8 6 0 7 5 1 2 inf
% 1 inf 7 0 inf inf 9 inf
% inf 1 5 inf 0 3 inf 8
% inf inf 1 inf 3 0 4 6
% inf inf 2 9 inf 4 0 3
% inf inf inf inf 8 6 3 0];
D=A;n=length(D);
for i=1:n
for j=1:n
R(i,j)=i;%赋路径初值
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)
A矩阵是邻接矩阵,对角线上为o,其余位置数字表示的是两点之间距离,比如A(1,2)=2,表示从第一个点到第二个点的距离为2.inf是无穷大的意思,这里表示没有直接沟通这两点的路.
n=length(D);设定n为D矩阵的长度.
接下来的两重循环,得到的R矩阵是n*n的矩阵,它每个数据表示的是路径,比如：R(1,3)=1;表示路径为：1-1-3.这里是初始化路径了.
后面的三重循环是floyd算法的关键所在,就是更新路线了.里面的那个判断指的是：
假设有3个点,1 2 3；如果我从1-2-3之间总距离小于1-3的距离,那么我R(1,3)=2；这就是选取更近的路线了.
最后的两个判断是为了不让曾经走过的点再次被遍历.就是不回头的意思了,这个一般都可以忽略了,你照打上去就是了.
不知道这样的解释你是否满意.
再问： 额，矩阵R保存的是路线么？怎么看。。。
再答： 是的 你在历史窗口看啊 你matlab界面不清楚么？
再问： 我的意思是R矩阵的结果出来了怎么看它表示的最短路径是哪一条？ R：
再答： 比如我选择从1到8的最短距离，那么首先看到的是第1行第8列，是5，然后是第一行第5列，是2，然后是1行2列是1，所以最短路径是1258
n=length(D);设定n为D矩阵的长度.
接下来的两重循环,得到的R矩阵是n*n的矩阵,它每个数据表示的是路径,比如：R(1,3)=1;表示路径为：1-1-3.这里是初始化路径了.
后面的三重循环是floyd算法的关键所在,就是更新路线了.里面的那个判断指的是：
假设有3个点,1 2 3；如果我从1-2-3之间总距离小于1-3的距离,那么我R(1,3)=2；这就是选取更近的路线了.
最后的两个判断是为了不让曾经走过的点再次被遍历.就是不回头的意思了,这个一般都可以忽略了,你照打上去就是了.
不知道这样的解释你是否满意.
再问： 额，矩阵R保存的是路线么？怎么看。。。
再答： 是的 你在历史窗口看啊 你matlab界面不清楚么？
再问： 我的意思是R矩阵的结果出来了怎么看它表示的最短路径是哪一条？ R：
再答： 比如我选择从1到8的最短距离，那么首先看到的是第1行第8列，是5，然后是第一行第5列，是2，然后是1行2列是1，所以最短路径是1258