數(shù)學(xué)模型floyd算法.ppt

1、Tsinghua University,Uncertainty Theory Laboratory,1,最短路算法,任意一對(duì)頂點(diǎn)之間的最短路算法:Floyd算法,Tsinghua University,Uncertainty Theory Laboratory,2,1、求距離矩陣的方法,2、求路徑矩陣的方法,3、查找最短路路徑的方法,一）算法的基本思想,三）算法步驟,Tsinghua University,Uncertainty Theory Laboratory,3,算法的基本思想,Tsinghua University,Uncertainty Theory Laboratory,4,算法原

2、理 求距離矩陣的方法,Tsinghua University,Uncertainty Theory Laboratory,5,算法原理 求路徑矩陣的方法,在建立距離矩陣的同時(shí)可建立路徑矩陣R,即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑,Tsinghua University,Uncertainty Theory Laboratory,6,算法原理 查找最短路路徑的方法,pk,p2,p1,p3,q1,q2,qm,則由點(diǎn)i到j(luò)的最短路的路徑為,Tsinghua University,Uncertainty Theory Labo

3、ratory,7,算法步驟,自定義floyd函數(shù),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(

4、w,選址問(wèn)題-中心問(wèn)題,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,Tsinghua University,Uncertainty Theory Laboratory,11,S(v1)=10, S(v2)=7, S(v3)=6

5、, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5,S(v3)=6,故應(yīng)將消防站設(shè)在v3處,Tsinghua University,Uncertainty Theory Laboratory,12,選址問(wèn)題-重心問(wèn)題,Tsinghua University,Uncertainty Theory Laboratory,13,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,in

6、f,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,Tsinghua University,Uncertainty Theory Laboratory,14,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

7、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,Tsinghua University,Uncertainty Theory Laboratory,15,實(shí)驗(yàn)八、最佳災(zāi)情巡視路線（節(jié)選部分,實(shí)驗(yàn)內(nèi)容： 求出下圖中O到其它各點(diǎn)的最短路線（要求求出最短路線及其最短距離） （節(jié)選了教材