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

1、通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告信息與通信工程學(xué)院通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告班級(jí)： 姓名： 學(xué)號(hào)： 序號(hào)： 第10頁(yè) 實(shí)驗(yàn)四floyd算法一、實(shí)驗(yàn)?zāi)康膄loyd算法通過(guò)圖的權(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算法可描述如下：給定圖及其邊的權(quán)f0：初始化距離矩陣和路由矩陣。其中：f1：已求得和，依據(jù)下面的迭代求和f2

2、：若，重復(fù)f1；若，終止。三、 實(shí)驗(yàn)內(nèi)容用matlab仿真工具實(shí)現(xiàn)floyd算法：給定圖及其邊的權(quán)，求出其各個(gè)端點(diǎn)之間的最小距離以及路由。1、分別用以下兩個(gè)初始距離矩陣表示的圖進(jìn)行算法驗(yàn)證：分別求出和。2、根據(jù)最短路由矩陣查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由（1）最短距離可以從最短距離矩陣的中直接得出；（2） 相應(yīng)的路由則可以通過(guò)在路由矩陣中查找得出。由于該程序中使用的是前向矩陣，因此在查找的過(guò)程中，路由矩陣中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

3、為例，求其最短距離和路由；對(duì)圖2，分別以端點(diǎn)對(duì)v1和v7，v3和v5，v1和v6為例，求其最短距離和路由。3、輸入一鄰接權(quán)值矩陣，求解最短距離和路由矩陣，及某些點(diǎn)間的最短路徑。4、擴(kuò)展的實(shí)驗(yàn)內(nèi)容（選作部分）（1）實(shí)現(xiàn)floyd算法的回溯路由矩陣；（2）探討可降低算法復(fù)雜度的算法。四、程序基本信息1、設(shè)計(jì)語(yǔ)言及開(kāi)發(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語(yǔ)言編寫(xiě)，程序文件名為floyd.m。第一部分：floyd算法求出其各個(gè)端點(diǎn)之間的最小距離以及路由這里

4、包含兩種路由方法的floyd算法：前向路由和回溯路由。下面先介紹其中的前向路由方法部分。它的主要思想及流程在實(shí)驗(yàn)原理部分已給出，下頁(yè)以流程圖的形式給出該段程序的工作流程，和原算法本身相比并無(wú)太多不同?；厮萋酚煞椒ǖ膄loyd算法流程如下：f0：初始化距離矩陣和路由矩陣。其中：f1：已求得和，依據(jù)下面的迭代求和f2：若，重復(fù)f1；若，終止?？梢?jiàn)該算法僅在路由矩陣更新方面有些許不同，因此這里不再給出它的流程圖。另外要說(shuō)明的一點(diǎn)是，程序中無(wú)法表示，用100代替。floyd算法（前向路由）流程圖第二部分：floyd算法程序改進(jìn)floyd算法中，距離矩陣每次更新的元素非常少（相對(duì)于矩陣元素總個(gè)數(shù)而言），

5、而路由矩陣又隨著距離矩陣的更新而更新。原先的程序中無(wú)論是否更新都要執(zhí)行一次賦值操作，其實(shí)只需要保留需要更新值的賦值操作，不更新值的賦值操作沒(méi)有意義。因此優(yōu)化后的程序可以大大減少賦值次數(shù)。這個(gè)程序其實(shí)沒(méi)有改變?cè)惴ㄋ枷?，只是針?duì)程序本身進(jìn)行了優(yōu)化。第三部分：查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由這段算法非常簡(jiǎn)單，主要利用了floyd算法生成的距離矩陣和路由矩陣，以下簡(jiǎn)述它的工作流程：五、程序運(yùn)行結(jié)果與分析1、利用給定的兩個(gè)路由矩陣判定算法正確性：矩陣1的執(zhí)行結(jié)果：矩陣2的執(zhí)行結(jié)果：注：上面的運(yùn)行結(jié)果中，w1為最短距離矩陣，r1為最短路由（前向）矩陣，r2為最短路由（回溯）矩陣。2、根據(jù)最短路由矩陣查詢?nèi)?/p>

6、意兩點(diǎn)間的最短距離和路由：以下查詢均使用前向最短路由矩陣。矩陣1：v4到v6，v3到v4。即v4到v6的最短距離：6.8，最短路由：v4v1v7v2v6；v3到v4的最短距離：3.2，最短路由：v3v7v1v4。矩陣2：v1到v7，v3到v5，v1到v6。即v1到v7的最短距離：5.1，最短路由：v1v3v7；v3到v5的最短距離：3.7，最短路由：v3v1v2v5；v1到v6的最短距離：8.4，最短路由：v1v2v5v6。3、原程序與改進(jìn)后的程序運(yùn)行結(jié)果及時(shí)間比較：采用矩陣1進(jìn)行測(cè)試。測(cè)試時(shí)，原程序的回溯矩陣處理語(yǔ)句被注釋掉，即不讓它處理回溯矩陣，同時(shí)兩個(gè)程序的初始化矩陣w0和r0的時(shí)間都不

7、考慮。原程序運(yùn)行結(jié)果：改進(jìn)后程序運(yùn)行結(jié)果： 這里僅給出一次運(yùn)行的結(jié)果。由上圖可見(jiàn)，兩個(gè)算法的運(yùn)行結(jié)果是完全相同的（路由矩陣對(duì)角線上的元素不同，但是實(shí)際應(yīng)用時(shí)對(duì)角線上的元素值沒(méi)有意義），且優(yōu)化后的程序執(zhí)行時(shí)間比未優(yōu)化的程序短。當(dāng)然，每次運(yùn)行結(jié)果都是不同的，有極小的可能會(huì)出現(xiàn)二者執(zhí)行時(shí)間近似甚至優(yōu)化后程序超過(guò)未優(yōu)化程序。由于時(shí)間所限，無(wú)法對(duì)每次的運(yùn)行時(shí)間加以統(tǒng)計(jì)，但大致上，優(yōu)化后程序平均起來(lái)運(yùn)行時(shí)間要比未優(yōu)化的程序短20%到30%。對(duì)于階數(shù)較大的輸入矩陣，優(yōu)化后程序的性能提升更為明顯。六、遇到的主要問(wèn)題1、wk和rk矩陣的表示問(wèn)題兩個(gè)矩陣本身是二維的，又要考慮一個(gè)k變量，因此采用三維數(shù)組。另外由于w和r矩陣都有一個(gè)初始矩陣w0和r0，因此k取值范圍為1到n+1（n為方陣階數(shù)）。2、多次執(zhí)行查詢兩點(diǎn)間最