数学模型floyd算法

《数学模型floyd算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最　短　路　算　法任意一对顶点之间的最短路算法:Floyd算法TsinghuaUniversity1UncertaintyTheoryLaboratory1、求距离矩阵的方法2、求路径矩阵的方法3、查找最短路路径的方法（一）算法的基本思想（三）算法步骤TsinghuaUniversity2UncertaintyTheoryLaboratory算法的基本思想TsinghuaUniversity3UncertaintyTheoryLaboratory算法原理——求距离矩阵的方法TsinghuaUniversity4U

2、ncertaintyTheoryLaboratory算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．TsinghuaUniversity5UncertaintyTheoryLaboratoryij算法原理——查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：TsinghuaUniversity6UncertaintyTheoryLaboratory算法步骤Tsi

3、nghuaUniversity7UncertaintyTheoryLaboratory自定义floyd函数function[d,r]=floyd(w)n=length(w);fori=1:nforj=1:nd(i,j)=w(i,j);r(i,j)=j;endendfork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)

4、oratoryclear;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)TsinghuaUniversity9UncertaintyTheoryLaboratory选址问题--中心问题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

5、,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)TsinghuaUniversity10UncertaintyTheoryLaboratoryS(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。TsinghuaUniversity11Uncertain

6、tyTheoryLaboratory选址问题--重心问题TsinghuaUniversity12UncertaintyTheoryLaboratoryclear;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、,7,1,6,1,4];fori=1:7m1=0;forj=1:7m1=m1+q(j)*d(i,j);endm(i)=m1;endmmin(m)TsinghuaUniversity13UncertaintyTheoryLaboratoryd=03.00005.00008.00007.00007.00008.50003.000002.00005.00004.00004.00005.50005.00002.000003.00002.00006.00007.50008.00005.00003.000001.00005.

8、00006.50007.00004.00002.00001.000004.00005.50007.00004.00006.00005.00004.000001.50008.50005.50007.50006.50005.50001.50000m=13278709270106130ans=70TsinghuaUniversity14UncertaintyTheoryLabo