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

1、实验四: Floyd算法 一、实验目的 利用MATLAB实现Floyd算法，可对输入的邻接距离矩阵计算图中任意两点 间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 Floyd算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵 求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两 个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算 大量数据。 Floyd算法可描述如下： 给定图G及其边（i , j ）的权叽j WiWn ,1WjWn） FO：初始化距离矩阵W和路由矩阵R。其中： 叫若eveE （有边） = co若勺;

2、e E （无边） 0若二j （对角线兀素） r（0）= J J若叫主s 一 0,其它| F1:已求得和R（kH,依据下面的迭代求旷和 唸二nun（就;吹严+吃“） 八匚們若叩严 F2：若 kWn,重 1F1；若 kn,终止。 三、实验内容 1、用MATLAB仿真工具实现Floyd算法：给定图G及其边（i , j ）的权 w,.j （1WiWn ,1WjWn）,求出其各个端点之间的最小距离以及路由。 （1）尽可能用M函数分别实现算法的关键部分，用M脚本来进行算法结 果验证; (2) 分别用以下两个初始距离矩阵表示的图进行算法验证: 0 100 100 1.2 9.2 100 0.5 _ 0 0.

3、5 2 1.5 100 100 100_ 100 0 100 5 100 3.1 2 0.5 0 100 100 1.2 9.2 100 100 100 0 100 100 4 1.5 2 100 0 100 5 100 3.1 1.2 5 100 0 6.7 100 100 W = 1.5 100 100 0 100 100 4 9.2 100 100 6.7 0 15.6 100 100 1.2 5 100 0 6.7 100 100 3.1 4 100 15.6 0 100 100 9.2 100 100 6.7 0 15.6 0.5 2 1.5 100 100 100 0 100 10

4、0 3.14 100 15.6 0 分别求出泸和R。 2、根据最短路由矩阵查询任意两点间的最短距离和路由 (1) 最短距离可以从最短距离矩阵的3 (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

5、、输入一邻接权值矩阵，求解罠短距离和路由矩阵，及某些点间的最短路径。 四、采用的语言 MatLab 源代码： function w r = fund (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; e I se 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 %根据

6、k-1次值和k次w值求出k次r值 for i=1:n for j=1:n if i=j r(i, j)二0; el seif w(i, j)a (i, j) r(i, j)=r(i,k); r(i, j)=r(i, j); end end end end; function P u=func2 (w,k1,k2) n = I eng th (w); U = w; m = 1; wh iIe m 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)

7、; 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 (P10); for j=I ength(wrow):(-1) : 1 P(k) = P1 (wrow(j); k=k+1; end P； w1=0 100 100100 ; 100 0 100 5 100 2； 100 100

8、 0 100 100 4 ； 5 100 0 100 100； 100 100 0 100; 100 4 100 0 100； 2 100 100 100 0; w2=02100 100 100; 0 100 100 100； 2 100 0 100 5 100 ; 100 100 0 100 100 4； 100 5 100 0 100; 100 100 100 0 ; 100 100 4 100 0; W1 R1 = fund (w1) W2 R2 = fund (w2) w二input (输入权值矩阵w=,); k1 = input(输入端点 1:k1 = ); k2=inputC输入端

9、点 2：k2=*); W R = fund (w) P u=func2 (w,k1,k2); disp ( k1 k2 间最短路:,num2str (P); disp(k1 x k2 间最短距离:,num2str (u); 五、数据结构 1.主要函数 聂短距离、路由函数： function w r = fund (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 end, end end; %迭代求出k次w值 for k=1:n

10、 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; el seif w(i, j)a (i, j) r(i, j)=r(i,k); else r (i, j)=r(i, j); end end end end; 最短路径函数： fund i on P u =func2 (w, k1, k2) n = I ength (w); m = 1; wh iIe m U(i,m)

11、+ 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(Pr=O); for j=Iength(wrow)

12、:(-1):1 P(k) = P1 (wrow(j); k=k+1; end P； 2.算法的流程图 Floyd算法： 六、实验结论与分析 Command Window m.1 W1 = 0 2. 5000 2. 0000 1.2000 7.9000 5.6000 0.5000 2. 5000 0 3. 5000 3.7000 10.4000 3. 1000 2.0000 2. 0000 3. 5000 0 3.2000 9.9000 4.0000 L.5000 1.2000 3. 7000 3. 2000 0 6.7000 S.8000 1.7000 7. 9000 10. 4000 9.

13、9000 6.7000 0 13.5000 8.4000 5. 6000 3. 1000 4. 0000 6.8000 13.5000 0 5. 1000 0. 5000 2. 0000 1. 5000 1.7000 8.4000 5. 1000 0 R1 = 0 4 4 J 1 0 一 6 i 0 6 1 1 1 0 5 1 1 4 4 4 4 0 4 4 2 2 3 2 2 0 2 1 2 3 1 1 2 0 A 通过上图可知,V4和V6之间最短距离是，最短路由是V4V1 V7V2V6, 3和V4之间最短距离是，最短路由是V3V7V1V4 Comma nd Window W2 = R2 =

14、 0 1 1 1 2 5 3 2 3 01 1 0 11 2 2 55 3 3 4 2 1 5 11 01 2 0 5 5 43 2 3 5 1 17 17 6 2 05 3 0 0 0.5000 2. 0000 1.5000 1.7000 8. 4000 5. 1000 0.5000 0 2. 5000 2.0000 1.2000 7. 9000 5.6000 2.0000 2.5000 0 3.5000 3.7000 10.4000 3. 1000 1.5000 2.0000 3. 5000 0 3.2000 9. 9000 4.0000 1.7000 L.2000 3. 7000 3.2

15、000 0 6. 7000 6.8000 8.4000 7.9000 10.4000 9.9000 6.7000 0 13.5000 5. 1000 5.6000 3. 1000 4.0000 6.8000 13. 5000 0 A| 通过上图可知，点对V1和V7之间最短距离是，最短路由是V1V3V7 端点对V3和V5之间最短距离是，最短路由是V3V1V2V5 端点对V1和V6之间最短距离是，最短路由是V1V2V5V6 Command Window m2 输入权伍拒阵inf irrf 5 inf inf: inf 0 3 irrf inf inf: inf 9 0 15 4 6 输入端点: 软入湍巨2:k2=6 8 4 irrf 0 inf inf: inf irrf 10 inf 0 w 二 0 Inf Inf 5 In Inf Inf0 3 Inf Inf Inf Inf9 0 15 4 6 8 1 Inf 0 Inf Inf Inf Inf 10 Inf 0 Inf Inf Inf 12 Inf Inf W = 09 12 5 16 IS 26 0 3 18 ( S 239 0 15 1 6 84 i 0 11 13 3319 10 25 0 16 fx3521 12 27 1