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

实验四：Floyd 算法一、实验目的利用MATLAB 实现Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理Floyd 算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算大量数据。 Floyd 算法可描述如下： 给定图G 及其边(i , j )的权wi, j (1in ,1jn) F0：初始化距离矩阵W(0)和路由矩阵R(0)。其中：F1：已求得W(k-1)和R(k-1)，依据下面的迭代求W(k)和R(k)F2：若kn，重复F1；若kn，终止。 三、实验内容1、用MATLAB 仿真工具实现Floyd 算法：给定图G 及其边(i , j )的权wi , j (1in ,1jn) ，求出其各个端点之间的最小距离以及路由。（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 源代码：【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, endend;%迭代求出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)a(i,j) r(i,j)=r(i,k); else r(i,j)=r(i,j); end end endend;【func2.m】function P u=func2(w,k1,k2)n = length(w);U = w;m = 1;while m U(i,m) + U(m,j) U(i,j) = U(i,m) + U(m,j); end end end m = m + 1;endu = 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 endendk=1;wrow = find(P1=0);for j=length(wrow):(-1):1 P(k) = P1(wrow(j); k=k+1;endP;【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; 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=);wW 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, endend;%迭代求出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)a(i,j) r(i,j)=r(i,k); else r(i,j)=r(i,j); end end endend;最短路径函数：function P u=func2(w,k1,k2)n = length(w);U = w;m = 1;while m U(i,m) + U(m,j) U(i,j) = U(i,m) + U(m,j); end end end m = m + 1;endu = 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 endendk=1;wrow = find(P1=0);for j=length(wrow):(-1):1 P(k) = P1(wrow(j); k=k+1;endP;2. 算法的流程图Floyd算法：结束开始Wi,j(k)=min(Wi,j(k-1) ,Wik(k -1) + Wkj(k -1) n=length(w)k=0kn?Wi,j(k)V1V7V2V6，3和V4之间最短距离是3.2，最短路由是V3V7V1V4通过上图可知，点对V1和V7之间最短距离是5.1，最短路由是V1V3V7端点对V3和V5之间最短距离是3.7，最短路由