数学模型floyd算法.ppt

《数学模型floyd算法.ppt》由会员分享，可在线阅读，更多相关《数学模型floyd算法.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数学模型与实验数学模型与实验最短路算法任意一对顶点之间的最短路算法任意一对顶点之间的最短路算法:Floyd:Floyd算法算法Tsinghua University1Uncertainty Theory Laboratory 数学模型与实验数学模型与实验1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤Tsinghua University2Uncertainty Theory Laboratory 数学模型与实验数学模型与实验算法的基本思想算法的基本思

2、想Tsinghua University3Uncertainty Theory Laboratory 数学模型与实验数学模型与实验算法原理算法原理 求距离矩阵的方法求距离矩阵的方法Tsinghua University4Uncertainty Theory Laboratory 数学模型与实验数学模型与实验算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径Tsinghua University5Uncertainty Theory Laborat

3、ory 数学模型与实验数学模型与实验ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：Tsinghua University6Uncertainty Theory Laboratory 数学模型与实验数学模型与实验算法步骤算法步骤Tsinghua University7Uncertainty Theory Laboratory自定义自定义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;endendfor

4、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 endendTsinghua University8Uncertainty Theory Laboratoryclear;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)Tsinghua University9Uncertainty Theory Laboratory 选址问题选址问题-中心问题中心问题clear;

5、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)Tsinghua University10Uncertainty Theory Laboratory 数学模型与实验数学模型与实验S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(

6、v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。Tsinghua University11Uncertainty Theory Laboratory 数学模型与实验数学模型与实验 选址问题选址问题-重心问题重心问题Tsinghua University12Uncertainty Theory Laboratory 数学模型与实验数学模型与实验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

7、,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;endmmin(m)Tsinghua University13Uncertainty Theory Laboratory 数学模型与实验数学模型与实验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

8、 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 0m=132 78 70 92 70 106 130ans=70Tsinghua University14Uncertainty Theory Laborator

9、y 数学模型与实验数学模型与实验实验八、最佳灾情巡视路线（节选部分）实验八、最佳灾情巡视路线（节选部分）实验内容：实验内容：求出下图中求出下图中O到其它各点的最短路线（要求求到其它各点的最短路线（要求求出最短路线及其最短距离）出最短路线及其最短距离）（节选了教材上（节选了教材上337面图中的面图中的16个点：即个点：即15、16、17、18、20、21、22、23、25、26、I、K、M、N、O、P等等16个点）个点）Tsinghua University15Uncertainty Theory Laboratory 数学模型与实验数学模型与实验Tsinghua University16Uncertainty Theory Laboratory