Floyd算法計(jì)算最短距離矩陣和路由矩陣查詢最短距離和路由matlab實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)四：Floyd 算法、實(shí)驗(yàn)?zāi)康睦肕ATLAB實(shí)現(xiàn)Floyd算法，可對輸入的鄰接距離矩陣計(jì)算圖中任意 兩點(diǎn)間的最短距離矩陣和路由矩陣，且能查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由。、實(shí)驗(yàn)原理Floyd算法適用于求解網(wǎng)絡(luò)中的任意兩點(diǎn)間的最短路徑：通過圖的權(quán)值矩陣 求出任意兩點(diǎn)間的最短距離矩陣和路由矩陣。優(yōu)點(diǎn)是容易理解，可以算出任意兩 個(gè)節(jié)點(diǎn)之間最短距離的算法，且程序容易實(shí)現(xiàn)，缺點(diǎn)是復(fù)雜度達(dá)到，不適合計(jì)算 大量數(shù)據(jù)。Floyd算法可描述如下: 給定圖G及其邊(i , j )的權(quán)wi, j (1 <i<n ,1 <j <n)F0:初始化距離矩陣 W（0）和路由矩陣R（°）

2、。其中:%若叨E f有邊） 丁若務(wù)任E 無邊）若匸/ （對用線元索）F1：已求得W（k-1）和R（k-1），依據(jù)下面的迭代求W（k）和R（k）噹二1何（屹7就T *賊穿）F2 :若kwn,重復(fù)F1;若k>n，終止。三、實(shí)驗(yàn)內(nèi)容1、用MATLAB仿真工具實(shí)現(xiàn)Floyd算法：給定圖G及其邊（i , j ）的權(quán)wi , j (1 <i<n ,1 <j<n)，求出其各個(gè)端點(diǎn)之間的最小距離以及路由。(1) 盡可能用M函數(shù)分別實(shí)現(xiàn)算法的關(guān)鍵部分，用 M腳本來進(jìn)行算法結(jié)果驗(yàn)證;(2)分別用以下兩個(gè)初始距離矩陣表示的圖進(jìn)行算法驗(yàn)證:Q 100 100 1.2 9.2 100 0.

3、5 "1000 100 5 1003.1 2100 100 0 100 1004 1.50 0.5 2 1.5 100 100 10010.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3,1L2 5 100 O6J 100 100護(hù)=1.5 100 1000 100 100 49.2 100 100'6.7 0 15.6 100100 1.2 5 100 0' 6.7 100100 3.1 4 100 15.6 0 100100 9.2 100 100 6.7 0 15.60.5 2 L5 100 100 100 0100 100

4、 3J 4 100 15,6 0 J分別求出 W(7)和R(7)。2、根據(jù)最短路由矩陣查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由(1)最短距離可以從最短距離矩陣的9(i,j)中直接得出;(2) 相應(yīng)的路由則可以通過在路由矩陣中查找得出。由于該程序中使用的是前向矩陣，因此在查找的過程中，路由矩陣中r(i,j)對應(yīng)的值為Vi到Vj路由上的下一個(gè)端點(diǎn)，這樣再代入r(r(i,j),j)，可得到下下個(gè)端點(diǎn)，由此不斷循環(huán)下去，即可找到最終 的路由。(3) 對圖1，分別以端點(diǎn)對V4和V6, V3和V4為例，求其最短距離和路由；對 圖2，分別以端點(diǎn)對V1和V7，V3和V5，V1和V6為例，求其最短距離和路由。3、輸入一鄰

5、接權(quán)值矩陣，求解最短距離和路由矩陣，及某些點(diǎn)間的最短路徑。四、采用的語言MatLab源代碼:【func1.m 】fun ctio n w r = fun c1(w)n=le ngth(w);x = w;r = zeros(n,1);% 路由矩陣的初始化for i=1:1:nfor j=1:1:nif x(i,j)=infr(i,j)=O;elser(i,j)=j;end.endend;%迭代求出k次w值for k=1: na=w;s = w;for i=1:nfor j=1: nw(i,j)=mi n( s(i,j),s(i,k)+s(k,j);end%根據(jù)k-1次值和k次w值求出k次r值 f

6、or i=1:nfor j=1: nif i=jr(i,j)=O;elseif w(i,j)<a(i,j)r(i,j)=r(i,k);elser(i,j)=r(i,j)；endendendend;【func2.m 】fun ctio n P u=fu nc2(w,k1,k2)n = len gth(w);U = w;m = 1;while m <= nfor i = 1:n;for j = 1:n;U(i,j) = U(i,m) + U(m,j);endendend m = m + 1;endu = U(k1,k2);P1=zeros(1, n);k = 1;P 1(k) = k2

7、;V = on es(1, n) * 100;kk = k2;while kk=k1for i = 1:nV(1,i) = U(k1,kk) - w(i,kk);if V(1,i) = U(k1,i)P 1(k+1)=i;kk=i;k=k+1;endendk=1;wrow = find(P 1=0);for j=le ngth(wrow):(-1):1P(k) = P1(wrow(j);k=k+1;endP；【m1.m】w1=0 100 100 1.2 9.2 100 0.5;100 0 100 5 100 3.1 2;100 100 0 100 100 4 1.5;1.2 5 100 0 6

8、.7 100 100;9.2 100 100 6.7 0 15.6 100;100 3.1 4 100 15.6 0 100;0.5 2 1.5 100 100 100 0;w2=0 0.5 2 1.5 100 100 100;0.5 0 100 100 1.2 9.2 100;2 100 0 100 5 100 3.1;r = zeros( n,1);%路由矩陣的初始化1.5 100 100 0 100 100 4;100 1.2 5 100 0 6.7 100;100 9.2 100 100 6.7 0 15.6;100 100 3.1 4 100 15.6 0;W1 R1 = fun c

9、1(w1)W2 R2 = fun c1(w2)【m2.m】for j=1:nw=i nput('輸入權(quán)值矩陣w=');k1=i nput('輸入端點(diǎn)1:k1=');k2=i nput('輸入端點(diǎn)2:k2=');W R = fun c1(w)P u=fu nc2(w,k1,k2);disp('k1、k2 間最短路：,num2str(P);disp('k1、k2 間最短距離：,num2str(u);五、數(shù)據(jù)結(jié)構(gòu)1.主要函數(shù)最短距離、路由函數(shù):fun cti on w r = fun c1(w) n=le ngth(w);for i=1

10、:1:nfor j=1:1:nif x(i,j)=100r(i,j)=0；elser(i,j)=j；end,end end;%迭代求岀k次w值 for k=1: na=w;s = w;for i=1: nfor j=1:nw(i,j)=mi n( s(i,j),s(i,k)+s(k,j);endend%根據(jù)k-1次值和k次w值求岀k次r值for i=1: nif i=jr(i,j)=O;elseif w(i,j)va(i,j)r(i,j)=r(i,k);elser(i,j)=r(i,j)；endendend end;最短路徑函數(shù):fun ctio n P u=fu nc2(w,k1,k2) n

11、 = len gth(w);U = w;m = 1;while m <= nfor i = 1:n;forj = 1:n;U(i,j) = U(i,m) + U(m,j);endendendm = m + 1;end u = U(k1,k2);P1=zeros(1, n);k = 1;P1(k) = k2;V = on es(1, n) * 100;kk = k2;while kk=k1for i = 1:nV(1,i) = U(k1,kk) - w(i,kk);if V(1,i) = U(k1,i)P1(k+1)=i;kk=i;k=k+1;endend end k=1;wrow = f

12、in d(P1=0);for j=le ngth(wrow):(-1):1P(k) = P1(wrow®);k=k+1;endP；2.算法的流程圖Floyd算法:II 結(jié)束六、實(shí)驗(yàn)結(jié)論與分析Cornnnand Windown.1W102. 50002. 00001.20007.&0005.SOOOO.SOOO2. 500003-50003. 700010*40003.10002-00001 OCO'O3. 500003.20009.90004.00001.E00OL 2C003.70003. 200000*7000S.30001.7000二 900010. 40009

13、.90006.7000013.50008.40005,0003* 0004- 00006.S00013*500005" 1000仇 50002. 00001.EOOO1.70003. 40005.10000R11420通過上圖可知,V4V6之間最短距離是6.8，最短路由是 V4 >V1 >V7>V2 >V6,3和V4之間最短距離是3.2，最短路由是V3 >V7 >V1 >V4Cornftiand Window¥200.50003. OOOO1.50fl01, VOCOS, 40005.10000.500002. 50002.0000

14、L 20IC07- 90005.SOOO2.00002.500003.甜前3. 70010. 40003. 10001.50002.0000玄 500003- 2000乳 90004.00001.70001.20003. 70003. 20()006. 70006. 3000S.40007.900010.40009.90006, ；0<30013.50005.10005.eooo3. 10004.00006. SOflO13. 50000E20254通過上圖可知,，點(diǎn)對V1V7之間最短距離是5.1，最短路由是V1 >V3端點(diǎn)對V1和V6之間最短距離是8.4，最短路由是V1 >

15、V2 >V5 >V6>V7端點(diǎn)對V3和V5之間最短距離是3.7,最短路由是V3 >V1 >V2 >V5» 2tt.兀収酋駆降*=0 inf inf 5 inffe汕端點(diǎn)l；Jtl=rinf irf 0 3 irf Lnf Lnf .inf 9 15 4 fli 15 4 inf 0 inf iirf; inf irrf lO :nf 0V 二0 InLLnf呂In£:nfInf03InfInf：n£hi!3015e&4Inf0Inf:nfInf Inf10Lif:nfTn-fInf12InfInfCt -0審12b*bIS26ISJ1ft1c2350151e3i70u13：3 310；5niLA352112n 一