北郵信息工程通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)4報(bào)告——Floyd算法

1、 信息與通信工程學(xué)院 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 班級(jí)： 姓名： 學(xué)號(hào)： 序號(hào)： 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)四Floyd 算法 一、實(shí)驗(yàn)?zāi)康?Floyd 算法通過圖的權(quán)值矩陣求出任意兩點(diǎn)間的最短距離矩陣和路由矩陣。優(yōu)點(diǎn)是容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間最短距離的算法，且程序容易實(shí)現(xiàn)，缺點(diǎn)是復(fù)雜度達(dá)到 ，不適合計(jì)算大量數(shù)據(jù)。 本次實(shí)驗(yàn)要求利用 MATLAB 實(shí)現(xiàn) Floyd 算法，可對(duì)輸入的鄰接距離矩陣計(jì)算圖中任意兩點(diǎn)間的最短距離矩陣和路由矩陣，且能查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由。 二、 實(shí)驗(yàn)原理 Floyd 算法可描述如下： 給定圖 G 及其邊 (i, j ) 的權(quán) wi , j (1 i n

2、,1 j n) F0：初始化距離矩陣 W (0) 和路由矩陣 R(0) 。其中： wij 若 eij wij (0) 若 eij 0 若 i j E （有邊） E （無邊） ( 對(duì)角線元素 ) (0) j 若 wij (0) rij 0, 其它 F1：已求得 W ( k -1) 和 R( k-1) ，依據(jù)下面的迭代求 W ( k ) 和 R( k ) wi(,kj )min( wi(,kj 1) , wi(,kk 1)w(kk, -j1) ) ri , j (k ) ri ,k(k 1) 若 wi , j ( k) wi , j ( k 1) ri , j ( k 1) 若 wi , j (k

3、 ) wi , j ( k 1) F2：若 k n ，重復(fù) F1；若 k n ，終止。 第 1 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 三、 實(shí)驗(yàn)內(nèi)容 用MATLAB仿 真 工 具 實(shí) 現(xiàn)Floyd 算 法 ： 給 定 圖 G 及 其 邊 (i ,j )的 權(quán) wi , j (1in , 1 jn ，)求出其各個(gè)端點(diǎn)之間的最小距離以及路由。 1、分別用以下兩個(gè)初始距離矩陣表示的圖進(jìn)行算法驗(yàn)證： 0 100 100 1.2 9.2 100 0.5 0 0.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

4、 100 100 4 1.5 2 100 0 100 5 100 3.1 W (0) 1.2 5 100 0 6.7 100 100 W (0) 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 100 3.1 4 100 15.6 0 分別求出 W (7) 和 R(7) 。 2、根據(jù)最短路由矩陣查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由 （1）最短

5、距離可以從最短距離矩陣的i, j 中直接得出； （2） 相應(yīng)的路由則可以通過在路由矩陣中查找得出。由于該程序中使用 的是前向矩陣，因此在查找的過程中，路由矩陣中 r(i,j) 對(duì)應(yīng)的值為 Vi 到 Vj 路由上的下一個(gè)端點(diǎn)，這樣再代入 r(r(i,j),j) ，可得到下下個(gè)端點(diǎn)，由此不斷循環(huán)下去，即可找到最終的路由。 （3）對(duì)圖 1，分別以端點(diǎn)對(duì) V4 和 V6, V3 和 V4 為例，求其最短距離和路由；對(duì)圖 2，分別以端點(diǎn)對(duì) V1 和 V7 ，V3 和 V5， V1 和 V6 為例，求其最短距離和路由。 3、輸入一鄰接權(quán)值矩陣，求解最短距離和路由矩陣，及某些點(diǎn)間的最短路徑。 4、擴(kuò)展的實(shí)驗(yàn)

6、內(nèi)容（選作部分） （ 1）實(shí)現(xiàn) Floyd 算法的回溯路由矩陣； （ 2）探討可降低算法復(fù)雜度的算法。 第 2 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 四、程序基本信息 1、設(shè)計(jì)語言及開發(fā)工具： MATLAB 。 2、數(shù)據(jù)結(jié)構(gòu)： 本次實(shí)驗(yàn)涉及到了數(shù)據(jù)結(jié)構(gòu)中圖的相關(guān)內(nèi)容，如圖的遍歷等等。另外，實(shí)驗(yàn)中采用不定長(zhǎng)數(shù)組存儲(chǔ)算法的相關(guān)矩陣信息。 3、主要函數(shù)（算法）： 本程序采用 MATLAB 語言編寫，程序文件名為 Floyd.m。第一部分： Floyd 算法求出其各個(gè)端點(diǎn)之間的最小距離以及路由 這里包含兩種路由方法的 Floyd 算法：前向路由和回溯路由。下面先介紹其中的前向路由方法部分。它的主要思想及流程在實(shí)

7、驗(yàn)原理部分已給出，下頁以流程圖的形式給出該段程序的工作流程，和原算法本身相比并無太多不同。 回溯路由方法的 Floyd 算法流程如下： F0：初始化距離矩陣 W (0) 和路由矩陣 R(0) 。其中： w 若 e ij ij w (0) 若 e ij ij 0 若 i j (0) i 若 w ij (0) rij 0, 其它 E （有邊） E （無邊） ( 對(duì)角線元素 ) F1：已求得 W ( k -1) 和 R( k-1) ，依據(jù)下面的迭代求 W ( k ) 和 R( k ) wi(,kj )min( wi(,kj 1) , wi(,kk 1)w(kk, -j1) ) (k ) rk(,kj

8、 1) 若 wi , j ( k) wi , j ( k 1) ri , j ri , j ( k 1) 若 wi , j (k ) wi , j ( k 1) F2：若 k n ，重復(fù) F1；若 k n ，終止。 可見該算法僅在路由矩陣更新方面有些許不同，因此這里不再給出它的流程圖。 另外要說明的一點(diǎn)是，程序中無法表示，用100 代替。 第 3 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 開始 獲取輸入的距 離矩陣階數(shù)n 輸入的矩陣作 為距離矩陣W0 構(gòu)造 n 階全 0矩 陣 R0，用于存儲(chǔ)路由信息 初始化矩陣 R0，若 W0中位置 (I,j)的元 素不為 100，則 R0 中對(duì)應(yīng)位置元素置 為j，否則為

9、0 置 k=1 產(chǎn)生矩陣 W k，方法： k k-1 k- W (i,j) 取 W(I,j) 和 W 1(i,k)+W k-1(k,j) 的較小值 產(chǎn)生矩陣 Rk，方法： 若 W k(I,j)n? 輸出矩陣 W k和 Rk 結(jié)束 Floyd 算法（前向路由）流程圖 第 4 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 第二部分： Floyd 算法程序改進(jìn) Floyd 算法中，距離矩陣每次更新的元素非常少（相對(duì)于矩陣元素總個(gè)數(shù)而言），而路由矩陣又隨著距離矩陣的更新而更新。原先的程序中無論是否更新都要執(zhí)行一次賦值操作，其實(shí)只需要保留需要更新值的賦值操作，不更新值的賦值操作沒有意義。因此優(yōu)化后的程序可以大大減少賦值次

10、數(shù)。這個(gè)程序其實(shí)沒有改變?cè)惴ㄋ枷耄皇轻槍?duì)程序本身進(jìn)行了優(yōu)化。 第三部分：查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由 這段算法非常簡(jiǎn)單，主要利用了 Floyd 算法生成的距離矩陣和路由矩陣，以下簡(jiǎn)述它的工作流程： 開始 輸入源端點(diǎn)i 和目的端點(diǎn)j 返回距離矩 陣位置為 (i,j) 的元素值即 最短距離 查詢路由矩陣 中位置為（ i,j) 的元素值 是 元素值為 j？ 否 記錄查詢到的 值，并將其賦給i 按順序返 回以上查 詢到的值 結(jié)束 第 5 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 五、程序運(yùn)行結(jié)果與分析 1、利用給定的兩個(gè)路由矩陣判定算法正確性： 0 100 100 1.2 9.2 100 0.5 0 0.5

11、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 W (0) 2 100 0 100 5 100 3.1 W (0) 1.2 5 100 0 6.7 100 100 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 1

12、00 100 3.1 4 100 15.6 0 矩陣 1 的執(zhí)行結(jié)果： 第 6 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 矩陣 2 的執(zhí)行結(jié)果： 注：上面的運(yùn)行結(jié)果中， W1 為最短距離矩陣， R1 為最短路由（前向）矩陣， R2 為最短路由（回溯）矩陣。 2、根據(jù)最短路由矩陣查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由： 以下查詢均使用前向最短路由矩陣。 矩陣 1：V4 到 V6，V3 到 V4。 第 7 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 即 V4 到 V6 的最短距離： 6.8，最短路由： V4V1V7V2V6； V3 到 V4 的最短距離： 3.2，最短路由： V3 V7 V1 V4 。 矩陣 2：V1 到 V7，V3

13、到 V5，V1 到 V6。 即 V1 到 V7 的最短距離： 5.1，最短路由： V1 V3 V7 ； V3 到 V5 的最短距離： 3.7，最短路由： V3 V1V2 V5 ； V1 到 V6 的最短距離： 8.4，最短路由： V1 V2V5 V6 。 3、原程序與改進(jìn)后的程序運(yùn)行結(jié)果及時(shí)間比較： 采用矩陣 1 進(jìn)行測(cè)試。 測(cè)試時(shí)，原程序的回溯矩陣處理語句被注釋掉，即不讓它處理回溯矩陣，同時(shí)兩個(gè)程序的初始化矩陣 W 0 和 R0 的時(shí)間都不考慮。 原程序運(yùn)行結(jié)果： 第 8 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 改進(jìn)后程序運(yùn)行結(jié)果： 第 9 頁 通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告 這里僅給出一次運(yùn)行的結(jié)果。由上圖可見，兩個(gè)算法的運(yùn)行結(jié)果是完全相同的（路由矩陣對(duì)角線上的元素不同，但是實(shí)際應(yīng)用時(shí)對(duì)角線上的元素值沒有意義），且優(yōu)化后的程序執(zhí)行時(shí)間比未優(yōu)化的程序短。當(dāng)然，每次運(yùn)行結(jié)果都是不同的，有極小的可能會(huì)出現(xiàn)二者執(zhí)行時(shí)間近似甚至優(yōu)化后程序超過未優(yōu)化程序。由于時(shí)間所限，無法對(duì)每次的運(yùn)行時(shí)間加以統(tǒng)計(jì)，但大致上，優(yōu)化后程 序平均起來運(yùn)行時(shí)間要比未優(yōu)化的程序短 20%到 30%。對(duì)于階數(shù)較大的輸入矩陣，優(yōu)化后程序的性能提升更為明顯。 六、遇到的主要問題 、 W k 和 Rk 矩陣的表示問題 1 兩個(gè)矩陣本身是