数学建模floyd算法最短路算法详解.ppt

算法原理—— 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R． 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径． i j 算法原理—— 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为： 算法步骤 自定义floyd函数 function [d,r]=floyd(w) n=length(w); for i=1:n for j=1:n d(i,j)=w(i,j); r(i,j)=j; end end for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=k; end end end end clear; w=[0,9,inf,3,inf;9,0,2,inf,7;inf,2,0,2,4;3,inf,2,0,inf;inf,7,4,inf,0]; [d,r]=floyd(w) 选址问题--中心问题 clear; w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0]; [d,r]=floyd(w) S=max(d’) %求矩阵各列的最大值 s=min(S) S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5 S(v3)=6,故应将消防站设在v3处。 选址问题--重心问题 clear; w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,inf,4,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,1,inf,inf;inf,inf,2,1,0,4,inf;inf,4,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0]; [d,r]=floyd(w) q=[3,2,7,1,6,1,4]; for i=1:7 m1=0; for j=1:7 m1=m1+q(j)*d(i,j); end m(i)=m1; end m min(m) d = 　　0 3.0000 5.0000 8.0000 7.0000 7.0000 8.5000 3.0000 0 2.0000 5.0000 4.0000 4.0000 5.5000 5.0000 2.0000 0 3.0000 2.0000 6.0000 7.5000 8.0000 5.0000 3.0000 0 1.0000 5.0000 6.5000 7.0000 4.0000 2.0000 1.0000 0 4.0000 5.5000 7.0000 4.0000 6.0000 5.0000 4.0000 0 1.5000 8.5000 5.5000 7.5000 6.5000 5.5000 1.5000 0 m =132 78 70 92 70 106 130 ans =70 实验八、最佳灾情巡视路线（节选部分） 实验内容： 求出下图中O到其它各点的最短路线（要求求出最短路线及其最短距离） （节选了教材上337面图中的16个点：即15、16、17、18、20、21、22、23、25、26、I、K、M、N、O、P等16个点） lzb8401552@hgnu.edu.cn lzb8401552@hgnu.edu.cn lzb8401552@hgnu.edu.cn lzb8401552@hgnu.edu.cn lzb8401552@hgnu.edu.c