Floyd算法_計算最短距離矩陣和路由矩陣_查詢最短距離和路由_matlab實驗報告

1、實驗四: Floyd算法 一、實驗目的 利用MATLAB實現(xiàn)Floyd算法，可對輸入的鄰接距離矩陣計算圖中任意兩點 間的最短距離矩陣和路由矩陣，且能查詢?nèi)我鈨牲c間的最短距離和路由。 二、實驗原理 Floyd算法適用于求解網(wǎng)絡中的任意兩點間的最短路徑：通過圖的權值矩陣 求出任意兩點間的最短距離矩陣和路由矩陣。優(yōu)點是容易理解，可以算出任意兩 個節(jié)點之間最短距離的算法，且程序容易實現(xiàn)，缺點是復雜度達到，不適合計算 大量數(shù)據(jù)。 Floyd算法可描述如下： 給定圖G及其邊（i , j ）的權嘰j WiWn ,1WjWn） FO：初始化距離矩陣W和路由矩陣R。其中： 叫若eveE （有邊） = co若勺;

2、e E （無邊） 0若二j （對角線兀素） r（0）= J J若叫主s 一 0,其它| F1:已求得和R（kH,依據(jù)下面的迭代求曠和 唸二nun（就;吹嚴+吃“） 八匚們?nèi)暨祰?F2：若 kWn,重 1F1；若 kn,終止。 三、實驗內(nèi)容 1、用MATLAB仿真工具實現(xiàn)Floyd算法：給定圖G及其邊（i , j ）的權 w,.j （1WiWn ,1WjWn）,求出其各個端點之間的最小距離以及路由。 （1）盡可能用M函數(shù)分別實現(xiàn)算法的關鍵部分，用M腳本來進行算法結 果驗證; (2) 分別用以下兩個初始距離矩陣表示的圖進行算法驗證: 0 100 100 1.2 9.2 100 0.5 _ 0 0.

3、5 2 1.5 100 100 100_ 100 0 100 5 100 3.1 2 0.5 0 100 100 1.2 9.2 100 100 100 0 100 100 4 1.5 2 100 0 100 5 100 3.1 1.2 5 100 0 6.7 100 100 W = 1.5 100 100 0 100 100 4 9.2 100 100 6.7 0 15.6 100 100 1.2 5 100 0 6.7 100 100 3.1 4 100 15.6 0 100 100 9.2 100 100 6.7 0 15.6 0.5 2 1.5 100 100 100 0 100 10

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

5、、輸入一鄰接權值矩陣，求解罠短距離和路由矩陣，及某些點間的最短路徑。 四、采用的語言 MatLab 源代碼： function w r = fund (w) n=length(w); x = w; r = zeros (n, 1) ;%路由矩陣的初始化 for i=1:1:n for j=1:1:n if x(i, j)=inf r(i, j)二0; e I se end, end end; %迭代求出k次W值 for k=1:n a 二w; s = w; for i=1:n for j=1:n w(i, j)=min(s(i, j), s(i, k)+s(k, j); end end %根據(jù)

6、k-1次值和k次w值求出k次r值 for i=1:n for j=1:n if i=j r(i, j)二0; el seif w(i, j)a (i, j) r(i, j)=r(i,k); r(i, j)=r(i, j); end end end end; function P u=func2 (w,k1,k2) n = I eng th (w); U = w; m = 1; wh iIe m U(i,m) + U(m, j) U(i, j) = U(i,m) + U(m, j); end end end m = m + 1; end u = U(k1,k2); P1=zeros (1, n)

7、; k = 1; P1 (k) = k2； V = ones (1, n) * 100; kk = k2; while kk=k1 for i = 1:n V(1, i) = U(k1,kk) - w(i,kk); if V(1, i) = U(k1, i) P1 (k+1) = i; kk=i; k二k+1; end end end k=1; wrow = find (P10); for j=I ength(wrow):(-1) : 1 P(k) = P1 (wrow(j); k=k+1; end P； w1=0 100 100100 ; 100 0 100 5 100 2； 100 100

8、 0 100 100 4 ； 5 100 0 100 100； 100 100 0 100; 100 4 100 0 100； 2 100 100 100 0; w2=02100 100 100; 0 100 100 100； 2 100 0 100 5 100 ; 100 100 0 100 100 4； 100 5 100 0 100; 100 100 100 0 ; 100 100 4 100 0; W1 R1 = fund (w1) W2 R2 = fund (w2) w二input (輸入權值矩陣w=,); k1 = input(輸入端點 1:k1 = ); k2=inputC輸入端

9、點 2：k2=*); W R = fund (w) P u=func2 (w,k1,k2); disp ( k1 k2 間最短路:,num2str (P); disp(k1 x k2 間最短距離:,num2str (u); 五、數(shù)據(jù)結構 1.主要函數(shù) 聶短距離、路由函數(shù)： function w r = fund (w) ( n=length(w); x = w; r = zeros (n, 1) ;%路由矩陣的初始化 for i=1：1：n for j=1:1:n if x(i, j)=100 r(i, j)二 0; else end, end end; %迭代求出k次w值 for k=1:n

10、 a=w； s = w; for i=1：n for j=1:n w(i, j)=min(s(i, j), s(i, k)+s(k, j); end end 塔根據(jù)k-1次值和k次w值求出k次r值 for i=1：n for j=1:n if i二二j r(i, j)二 0; el seif w(i, j)a (i, j) r(i, j)=r(i,k); else r (i, j)=r(i, j); end end end end; 最短路徑函數(shù)： fund i on P u =func2 (w, k1, k2) n = I ength (w); m = 1; wh iIe m U(i,m)

11、+ U(m, j) U(i, j) = U(i,m) + U(m, j); end end end m = m + 1 end u = U(k1,k2); P1=zeros (1, n); k = 1; P1 (k) = k2; V = ones(1, n) * 100； kk = k2； while kk=k1 for i = 1:n V(1, i) = U(k1,kk) - w(i,kk); if V(1, i) = U(k1, i) P1 (k+1)=i； kk=i; k=k+1; end end end k=1 wrow = find(Pr=O); for j=Iength(wrow)

12、:(-1):1 P(k) = P1 (wrow(j); k=k+1; end P； 2.算法的流程圖 Floyd算法： 六、實驗結論與分析 Command Window m.1 W1 = 0 2. 5000 2. 0000 1.2000 7.9000 5.6000 0.5000 2. 5000 0 3. 5000 3.7000 10.4000 3. 1000 2.0000 2. 0000 3. 5000 0 3.2000 9.9000 4.0000 L.5000 1.2000 3. 7000 3. 2000 0 6.7000 S.8000 1.7000 7. 9000 10. 4000 9.

13、9000 6.7000 0 13.5000 8.4000 5. 6000 3. 1000 4. 0000 6.8000 13.5000 0 5. 1000 0. 5000 2. 0000 1. 5000 1.7000 8.4000 5. 1000 0 R1 = 0 4 4 J 1 0 一 6 i 0 6 1 1 1 0 5 1 1 4 4 4 4 0 4 4 2 2 3 2 2 0 2 1 2 3 1 1 2 0 A 通過上圖可知,V4和V6之間最短距離是，最短路由是V4V1 V7V2V6, 3和V4之間最短距離是，最短路由是V3V7V1V4 Comma nd Window W2 = R2 =

14、 0 1 1 1 2 5 3 2 3 01 1 0 11 2 2 55 3 3 4 2 1 5 11 01 2 0 5 5 43 2 3 5 1 17 17 6 2 05 3 0 0 0.5000 2. 0000 1.5000 1.7000 8. 4000 5. 1000 0.5000 0 2. 5000 2.0000 1.2000 7. 9000 5.6000 2.0000 2.5000 0 3.5000 3.7000 10.4000 3. 1000 1.5000 2.0000 3. 5000 0 3.2000 9. 9000 4.0000 1.7000 L.2000 3. 7000 3.2

15、000 0 6. 7000 6.8000 8.4000 7.9000 10.4000 9.9000 6.7000 0 13.5000 5. 1000 5.6000 3. 1000 4.0000 6.8000 13. 5000 0 A| 通過上圖可知，點對V1和V7之間最短距離是，最短路由是V1V3V7 端點對V3和V5之間最短距離是，最短路由是V3V1V2V5 端點對V1和V6之間最短距離是，最短路由是V1V2V5V6 Command Window m2 輸入權伍拒陣inf irrf 5 inf inf: inf 0 3 irrf inf inf: inf 9 0 15 4 6 輸入端點: 軟入湍巨2:k2=6 8 4 irrf 0 inf inf: inf irrf 10 inf 0 w 二 0 Inf Inf 5 In Inf Inf0 3 Inf Inf Inf Inf9 0 15 4 6 8 1 Inf 0 Inf Inf Inf Inf 10 Inf 0 Inf Inf Inf 12 Inf Inf W = 09 12 5 16 IS 26 0 3 18 ( S 239 0 15 1 6 84 i 0 11 13 3319 10 25 0 16 fx3521 12 27 1