当前位置：文档之家 › Floyd算法_计算最短距离矩阵和路由矩阵_查询最短距离和路由_matlab实验报告

Floyd算法_计算最短距离矩阵和路由矩阵_查询最短距离和路由_matlab实验报告

  • 格式：doc
  • 大小：36.00 KB
  • 文档页数：7

文档收集于互联网，已重新整理排版.word版本可编辑,有帮助欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑. 实验四：Floyd 算法 一、实验目的 利用MATLAB 实现Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 Floyd 算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算大量数据。 Floyd 算法可描述如下： 给定图G 及其边(i , j )的权wi, j (1≤i≤n ,1≤j≤n)

F0：初始化距离矩阵W(0)和路由矩阵R(0)。其中： F1：已求得W(k-1)和R(k-1)，依据下面的迭代求W(k)和R(k) F2：若k≤n，重复F1；若k>n，终止。

三、实验内容

1、用MATLAB 仿真工具实现Floyd 算法：给定图G 及其边(i , j )的权 wi , j (1≤i≤n ,1≤j≤n) ，求出其各个端点之间的最小距离以及路由。 （1）尽可能用M 函数分别实现算法的关键部分，用M 脚本来进行算法结 果验证； （2）分别用以下两个初始距离矩阵表示的图进行算法验证： 分别求出W(7)和R(7)。 2、根据最短路由矩阵查询任意两点间的最短距离和路由 （1）最短距离可以从最短距离矩阵的ω(i,j)中直接得出； （2）相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi 到Vj 路由上的下一个端点，这样再代入r(r(i,j),j)，可得到下下个端点，由此不断循环下去， 即可找到最终的路由。 （3）对图1，分别以端点对V4 和V6, V3 和V4 为例，求其最短距离和路由； 对图2，分别以端点对V1 和V7，V3 和V5，V1 和V6 为例，求其最短距离和路由。 3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。

四、采用的语言 MatLab 源代码： 文档收集于互联网，已重新整理排版.word版本可编辑,有帮助欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑. 【func1.m】 function [w r] = func1(w) n=length(w); x = w; r = zeros(n,1);%路由矩阵的初始化 for i=1:1:n for j=1:1:n if x(i,j)==inf r(i,j)=0; else r(i,j)=j; end, end end; %迭代求出k次w值 for k=1:n a=w; s = w; for i=1:n for j=1:n w(i,j)=min(s(i,j),s(i,k)+s(k,j)); end end %根据k-1次值和k次w值求出k次r值 for i=1:n for j=1:n if i==j r(i,j)=0; elseif w(i,j)r(i,j)=r(i,k); else r(i,j)=r(i,j); end end end end; 【func2.m】 function [P u]=func2(w,k1,k2) n = length(w); U = w; m = 1; while m <= n for i = 1:n; for j = 1:n; 文档收集于互联网，已重新整理排版.word版本可编辑,有帮助欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑. if U(i,j)>U(i,m) + U(m,j) U(i,j) = U(i,m) + U(m,j); end end end m = m + 1; end u = U(k1,k2); P1=zeros(1,n); k = 1; P1(k) = k2; V = ones(1,n) * 100; kk = k2; while kk~=k1 for i = 1:n V(1,i) = U(k1,kk) - w(i,kk); if V(1,i) == U(k1,i) P1(k+1)=i; kk=i; k=k+1; end end end k=1; wrow = find(P1~=0); for j=length(wrow):(-1):1 P(k) = P1(wrow(j)); k=k+1; end P; 【m1.m】 w1=[0 100 100 1.2 9.2 100 0.5; 100 0 100 5 100 3.1 2; 100 100 0 100 100 4 1.5; 1.2 5 100 0 6.7 100 100; 9.2 100 100 6.7 0 15.6 100; 100 3.1 4 100 15.6 0 100; 0.5 2 1.5 100 100 100 0]; w2=[0 0.5 2 1.5 100 100 100; 0.5 0 100 100 1.2 9.2 100; 2 100 0 100 5 100 3.1; 1.5 100 100 0 100 100 4; 100 1.2 5 100 0 6.7 100; 100 9.2 100 100 6.7 0 15.6; 文档收集于互联网，已重新整理排版.word版本可编辑,有帮助欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑. 100 100 3.1 4 100 15.6 0]; [W1 R1] = func1(w1) [W2 R2] = func1(w2) 【m2.m】 w=input('输入权值矩阵w='); k1=input('输入端点1:k1='); k2=input('输入端点2:k2='); w [W R] = func1(w) [P u]=func2(w,k1,k2); disp(['k1、k2间最短路：',num2str(P)]); disp(['k1、k2间最短距离：',num2str(u)]);

五、数据结构 1.主要函数 最短距离、路由函数： function [w r] = func1(w) n=length(w); x = w; r = zeros(n,1);%路由矩阵的初始化 for i=1:1:n for j=1:1:n if x(i,j)==100 r(i,j)=0; else r(i,j)=j; end, end end; %迭代求出k次w值 for k=1:n a=w; s = w; for i=1:n for j=1:n w(i,j)=min(s(i,j),s(i,k)+s(k,j)); end end %根据k-1次值和k次w值求出k次r值 for i=1:n for j=1:n if i==j r(i,j)=0; 文档收集于互联网，已重新整理排版.word版本可编辑,有帮助欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑. elseif w(i,j) r(i,j)=r(i,k); else r(i,j)=r(i,j); end end end end; 最短路径函数： function [P u]=func2(w,k1,k2) n = length(w); U = w; m = 1; while m <= n for i = 1:n; for j = 1:n; if U(i,j)>U(i,m) + U(m,j) U(i,j) = U(i,m) + U(m,j); end end end m = m + 1; end u = U(k1,k2); P1=zeros(1,n); k = 1; P1(k) = k2; V = ones(1,n) * 100; kk = k2; while kk~=k1 for i = 1:n V(1,i) = U(k1,kk) - w(i,kk); if V(1,i) == U(k1,i) P1(k+1)=i; kk=i; k=k+1; end end end k=1; wrow = find(P1~=0); for j=length(wrow):(-1):1 P(k) = P1(wrow(j)); k=k+1; 文档收集于互联网，已重新整理排版.word版本可编辑,有帮助欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑. end P; 2. 算法的流程图 Floyd算法：

六、实验结论与分析 通过上图可知，V4和V6之间最短距离是6.8，最短路由是V4—>V1—>V7—>V2—>V6，3和V4之间最短距离是3.2，最短路由是V3—>V7—>V1—>V4 通过上图可知，，点对V1和V7之间最短距离是5.1，最短路由是V1—>V3—>V7 端点对V3和V5之间最短距离是3.7，最短路由是V3—>V1—>V2—>V5 端点对V1和V6之间最短距离是8.4，最短路由是V1—>V2—>V5—>V6

七、遇到的问题及解决方法

结束 开始 Wi,j(k)=min(Wi,j(k-1) ,Wik(k -1) + Wkj(k -1)) n=length(w) k=0

k≤n?

Wi,j(k)Wi,j(k)≤Wi,j(k-1)? Yes

ri,j(k)= ri,j(k-1) No ri,j(k)= ri,k(k-1) Yes

合集下载

floyd算法 matlab程序

floyd算法 matlab程序

Floyd算法算法能实现求一个图中任意两点间最断距离，并给出路径。

设图G的顶点数为n，D=(d ij)n×n，为其距离矩阵，Floyd算法步骤如下：Step 1：输入距离矩阵D；Step 2：k=1，Step 3：i=1；Step 4：d ij=min(d ij,d ik+d kj),j=1,2,…,n;Step 5：i++；如果i≤n，转Step 4；Step 6：k++；如果k≤n，转Step 3；否则转Step 7；Step 7：程序结束，输出结果。

用Floyd算法求图中各顶点之间的最短路的Matlab程序。

M=99999;a=[0,20,14,M,M,M,MM,0,M,15,12,M,MM,M,0,10,M,13,MM,M,M,0,8,M,9M,M,M,M,0,8,10M,M,M,M,M,0,12M,M,M,M,M,M,0];length=floyd(a)r代表任意城市之间经过的路径,这个结果比起Mathematica来说不好理解，这个也是我自己对比上面结果的理解。

第一行代表1经过1，2，3，4，5，6，7的路径；第一个数是1，代表1直接到1最短 （1，1）第二个数是2，代表1直接到2最短 （1，2）第三个数是3，代表1直接到3最短 （1，3）第四个数是3，代表1经过3再到4最短 （1，3，4）第五个数是2，代表1经过2再到5最短 （1，2，5）第六个数是3，代表1经过3再到6最短 （1，3，6）第七个数是3，代表1经过3再到7最短 （1，3，7）？？和前面不一样出现问题了，其实错误在于3不是直接到7最短造成的（我们取的3到7距离为99999） 而前面3个红色的路径是不会出现这种情况的（可以看下面的表）。

可以看第三行3是经过4再到7最短！ 所以（1，3，4，7）任意城市之间经过的路径我们只需要求红色括号里面的路径就可以了（用上面的分析可以得到答案），其他的已经是最短路了。

{ {1,1} {1,2} {1,3} {} {} {} {}{2,1} {2,2} {2,3} {2,4} {2,5} {2，5，6} {2，5，7}{3,1} {3,2} {3,3} {3,4} {3，4，5} {3,6} {3，4，7}{4,1} {4,2} {4,3} {4,4} {4,5} {4，5，6} {4,7}{5,1} {5,2} {5,3} {5,4} {5,5} {5,6} {5,7}{6,1} {6,2} {6,3} {6,4} {6,5} {6,6} {6,7}{7,1} {7,2} {7,3} {7,4} {7,5} {7,6} {7,7} }如果熟练后也可以很快得到结果！。

F算法

F算法

姓名：商晴庆 班级： 学号： 班内序号： 实验四 Floyd算法的matlab实现 一、程序及注释 function y=floyd(x) %the original floyd function disp('*************【Floyd算法】以第五章课后习题5.10为例********************'); stop=1; while(stop) disp('给定的测试初始距离矩阵为：'); w1=[0.0 9.2 1.1 3.5 100 100 1.3 0.0 4.7 100 7.2 100 2.5 100 0.0 100 1.8 100 100 100 5.3 2.4 0.0 7.5 100 6.4 2.2 8.9 0.0 5.1 7.7 100 2.7 100 2.1 0.0] w=input('您可以直接输入“w1”选择给定的测试矩阵，或者任意输入一个邻接权值矩阵进行测试w=: '); [n1,n1]=size(w); %初始化路由矩阵 %"tic" is used to save current time,"toc" can be used to record the time % when the program run out. tic; for i=1:n1 for j=1:n1 if w(i,j)~=100 && w(i,j)~=0 r1(i,j)=j; else r1(i,j)=0; end end end temp01=w;w1=w;w2=w; % update the distence matrix and the route matrix %judge every point whether it can be a transit or not for k=1:n1 for i=1:n1 for j=1:n1 w(i,j)=min([w(i,j),w(i,k)+w(k,j)]);%update the distance matrix temp02=temp01; temp01=w;% save the previous diantance matrix and the current distance matrix if temp01(i,j) r1(i,j)=r1(i,k);%update the route matrix end if temp01(i,j)==temp02(i,j) r1(i,j)=r1(i,j); end end end end % the end of the floyd arithmetic %save the running time t1=toc; %优化算法 tic; for i=1:n1 for j=1:n1 if w2(i,j)~=100&&w2(i,j)~=0 r2(i,j)=j; else r2(i,j)=0; end end end temp02=w2; for k=1:n1 for i=1:n1 for j=1:n1 if w2(i,j)>w2(i,k)+w2(k,j) %仅查找需要更新的距离矩阵元素 w2(i,j)=w2(i,k)+w2(k,j); %更新距离矩阵 r2(i,j)=r2(i,k);%更新前向路由矩阵 end end end end t2=toc;

floyd算法matlab代码

floyd算法matlab代码

function [D,R]=floyd(a)% a=[3 2;4 6];采用floyd算法计算图a中每对顶点最短路% a=[0 4 11;6 0 2;3 inf 0];n=size(a,1);D=a % D是距离矩阵for i=1:nfor j=1:nR(i,j)=j;endendR % R是路由矩阵for k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRend••••••••••••••••••【唯美句子】走累的时候，我就到升国旗哪里的一角台阶坐下，双手抚膝，再闭眼，让心灵受到阳光的洗涤。

懒洋洋的幸福。

顶 3 收藏 2•【唯美句子】一个人踮着脚尖，在窄窄的跑道白线上走，走到很远的地方又走回来。

阳光很好，温暖，柔和。

漫天的安静。

顶7 收藏7•【唯美句子】清风飘然，秋水缓淌。

一丝云起，一片叶落，剔透生命的空灵。

轻轻用手触摸，就点碎了河面的脸。

落叶舞步婀娜不肯去，是眷恋，是装点？瞬间回眸，点亮了生命精彩。

顶11 收藏9•【唯美句子】几只从南方归来的燕子，轻盈的飞来飞去，“几处早莺争暖树，谁家新燕啄春泥，”其乐融融的山林气息，与世无争的世外桃源，让人心旷神怡。

顶0 收藏 2•【唯美句子】流年清浅，岁月轮转，或许是冬天太过漫长，当一夜春风吹开万里柳时，心情也似乎开朗了许多，在一个风轻云淡的早晨，踏着初春的阳光，漫步在碧柳垂青的小河边，看小河的流水因为解开了冰冻而欢快的流淌，清澈见底的的河水，可以数得清河底的鹅软石，偶尔掠过水面的水鸟，让小河荡起一层层的涟漪。

河岸换上绿色的新装，刚刚睡醒的各种各样的花花草草，悄悄的露出了嫩芽，这儿一丛，那儿一簇，好像是交头接耳的议论着些什么，又好象是在偷偷地说着悄悄话。

顶 3 收藏 4•【唯美句子】喜欢海子写的面朝大海春暖花开，不仅仅是因为我喜欢看海，还喜欢诗人笔下的意境，每当夜深人静时，放一曲纯音乐，品一盏茶，在脑海中搜寻诗中的恬淡闲适。

弗洛伊德算法求解最短路径

弗洛伊德算法求解最短路径

弗洛伊德算法求解最短路径算法工作原理如下：1.初始化一个n×n的矩阵D，其中D[i][j]表示从节点i到节点j的最短路径长度。

若两节点之间无直接边相连，则用一个很大的值表示不可达。

2.对矩阵D进行初始化，令D[i][j]=w(i,j)，其中w(i,j)表示节点i到j的直接边的权重。

3.对于每对节点i和j，以节点k作为中间节点，更新矩阵D，若存在一条路径经过中间节点k，使得路径长度较之前更短，则更新D[i][j]=D[i][k]+D[k][j]。

4.重复步骤3，直到所有节点的最短路径长度被确定。

5.若存在一个k，使得D[k][k]的值为负数，则表示存在一个含有负权重环的路径，即最短路径的长度没有意义。

迭代的次数为n次，其中n为节点的个数。

每次迭代需要对所有的节点对(i,j)进行检查，以找出所有可能的最短路径。

下面是一个使用弗洛伊德算法求解最短路径的示例：```pythondef floydWarshall(graph):n = len(graph)D = graphfor k in range(n):for i in range(n):for j in range(n):if D[i][j] > D[i][k] + D[k][j]:D[i][j]=D[i][k]+D[k][j]return D#测试INF = float('inf') # 无穷大graph = [[0, 5, INF, 10],[INF,0,3,INF],[INF,INF,0,1],[INF,INF,INF,0]]result = floydWarshall(graph)for row in result:print(row)```在上述示例中，我们通过传入一个图的邻接矩阵作为参数，运行floydWarshall函数来求解最短路径。

其中INF表示不可达的情况。

输出结果为：```[0,5,8,9][inf, 0, 3, 4][inf, inf, 0, 1][inf, inf, inf, 0]```输出的矩阵中，每个元素D[i][j]表示从节点i到节点j的最短路径长度。