距離向量路由算法實(shí)驗(yàn)報(bào)告

1、 信息安全_專(zhuān)業(yè) 1002_班 2012年12月20日 姓名吳文珊 學(xué)號(hào)_09091025251 實(shí)驗(yàn)題目 模擬距離向量路由算法的路由表交換過(guò)程，演示每輪交換后路由表的變化，動(dòng)態(tài)生成網(wǎng)絡(luò)拓?fù)鋱D，從初始路由表開(kāi)始，進(jìn)行交換路由表，演示每輪交換后的路由表的變化。觀察和討論多少輪交換后路由表穩(wěn)定。2 需求分析本程序用C編寫(xiě)，完成距離向量路由算法的模擬。(1)輸入的形式與輸出值的范圍：輸入時(shí)要求輸入節(jié)點(diǎn)個(gè)數(shù)、初始網(wǎng)絡(luò)拓?fù)鋱D中邊的條數(shù)（即：鄰居節(jié)點(diǎn)的對(duì)數(shù)），節(jié)點(diǎn)名稱(chēng)、每條邊的弧頭、弧尾節(jié)點(diǎn)、邊權(quán)值。名字定義為字符串形式，節(jié)點(diǎn)個(gè)數(shù)、邊條數(shù)、邊權(quán)值為整形變量；(2)輸出的形式：輸入信息后，程序輸出每輪交換之

2、后新的的路由表(3)程序所能達(dá)到的功能：完成節(jié)點(diǎn)信息的輸入、隨機(jī)選取節(jié)點(diǎn)交換向量，并更新路由表，顯示經(jīng)過(guò)多少輪交換路由表穩(wěn)定，并停止交換。(4)測(cè)試數(shù)據(jù)：節(jié)點(diǎn)個(gè)數(shù)：4 邊條數(shù) ：4節(jié)點(diǎn)名稱(chēng)：a b c d 弧頭 弧尾 權(quán)值 a b 3 b d 6 c a 2 d a 6最終距離向量矩陣如下： a b c d a 0 3 2 6 b 3 0 5 6 c 2 5 0 8 d 6 6 8 03 概要設(shè)計(jì) (1)為了實(shí)現(xiàn)上述功能，須定義結(jié)構(gòu)體的抽象數(shù)據(jù)類(lèi)型(2)本程序包含了 個(gè)函數(shù)：void visit(VertexType ver)/訪問(wèn)頂點(diǎn)的函數(shù)void input(VertexType &ver

3、) /輸入頂點(diǎn)信息的函數(shù) int LocateVex(MGraph G,VertexType u)/查找頂點(diǎn)u,并返回void CreateDN(MGraph &G)/構(gòu)造有向網(wǎng)G GetVex(MGraph G，int v)/得到圖中頂點(diǎn)Vvoid Display(MGraph G)/顯示路由表void ShortestPath_Floyd()各函數(shù)間關(guān)系如下：CreateDN()LocateVex() visit()Main() Display() GetVex() ShortestPath_Floyd()4 詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的數(shù)據(jù)類(lèi)型，對(duì)每個(gè)操作給出偽碼算法。對(duì)主程序和其

4、他模塊也都需要寫(xiě)出偽碼算法。(1) 節(jié)點(diǎn)類(lèi)型 struct VertexType/最簡(jiǎn)單的頂點(diǎn)信息類(lèi)型(只有頂點(diǎn)名稱(chēng))char nameMAX_NAME;/頂點(diǎn)名稱(chēng) char routersMAX_VERTEX_NUMMAX_NAME;/定義最短路徑中到目的節(jié)點(diǎn)的上一跳 ;struct MGraph/圖的結(jié)構(gòu)VertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣(二維數(shù)組)int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind; /圖的種類(lèi)標(biāo)志 ;typedef struct /邊(弧)信息結(jié)構(gòu)VRType

5、 adj;/頂點(diǎn)關(guān)系類(lèi)型，對(duì)帶權(quán)圖，表示權(quán)值 struct VertexType/最簡(jiǎn)單的頂點(diǎn)信息類(lèi)型(只有頂點(diǎn)名稱(chēng))char nameMAX_NAME;/頂點(diǎn)名稱(chēng) char routersMAX_VERTEX_NUMMAX_NAME;/定義最短路徑中到目的節(jié)點(diǎn)的上一跳 ;struct MGraph/圖的結(jié)構(gòu)VertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣(二維數(shù)組)int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind; /圖的種類(lèi)標(biāo)志 ;(2)各功能函數(shù)偽碼算法 main() CreateDN(g

6、);/構(gòu)造有向網(wǎng)g for(i=0;ig.vexnum;i+) g.arcsii.adj=0;/頂點(diǎn)到自身距離為0 Display(g);/輸出有向網(wǎng)g ShortestPath_Floyd(g,p,d);/求每對(duì)頂點(diǎn)的最短路徑 return 1; void CreateDN(MGraph &G)/構(gòu)造有向網(wǎng)G scanf(%d %d,&G.vexnum,&G.arcnum); for(i=0;iG.vexnum;i+)/構(gòu)造頂點(diǎn)向量 input(G.vexsi); /輸入節(jié)點(diǎn)名稱(chēng) for(i=0;iG.vexnum;i+)/初始化二維鄰接矩陣 for(j=0;jG.vexnum;j+) G.

7、arcsij.adj=INFINITY; for(k=0;kG.arcnum;k+) scanf(%s %s %d,v1.nam,&w); 存入圖中； void Display(MGraph G)for(i=0;iG.vexnum;i+)visit(GetVex(G,i);for(i=0;iG.vexnum;i+) printf(%-8s,G.); for(j=0;jG.vexnum;j+) printf(%20s,G.); for(k=0;kG.vexnum;k+) printf( %-5d,G.arcsjk.adj); printf(n); void

8、 ShortestPath_Floyd()/用Floyd算法隨機(jī)更新兩頂點(diǎn)間最短路徑、頂點(diǎn)路由表，若Pvwu為true，則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+)Dvw=G.arcsvw.adj;/頂點(diǎn)v到w的直接距離for(u=0;uG.vexnum;u+)Pvwu=FALSE;if(DvwINFINITY)/從V到W有直接路徑 strcpy(G.vexsv.routersw,G.);Pvwv=Pvww=TRUE; /由v到w的路徑經(jīng)過(guò)v和w兩點(diǎn) else strcpy(G.vexsv.rou

9、tersw,-); srand(unsigned)time(NULL);/產(chǎn)生隨機(jī)數(shù)種子，防止偽隨機(jī)數(shù) while(change=1) for(;bad20;)/連續(xù)20次隨機(jī)交換無(wú)更新，為壞的交換，則停止隨機(jī)交換 v=rand()%G.vexnum;w=rand()%G.vexnum;if(DvwINFINITY&v!=w) change=0; for(u=0;uG.vexnum;u+) if(DwuINFINITY&Dvw+DwuDvu)/從v經(jīng)u到w的一條路徑更短 Dvu=Dvw+Dwu;/更新最短距離 change=1; bad=0; /一有更新，則不是壞的交換 if(w!=u) st

10、rcpy(G.vexsv.routersu,G.);/記錄上一跳節(jié)點(diǎn)名稱(chēng) for(i=0;iG.vexnum;i+) Pvwi=Pvui|Puwi;/從v到w的路徑經(jīng)過(guò)從v到u和從u到w的所有路徑 /if /for u if(change=1) stable+; for(j=0;jG.vexnum;j+) printf( %8s %8d %8sn,G.,Dvj,G.vexsv.routersj); / if change else bad+; /if/for /while for(i=0;iG.vexnum;i+) printf(%-8s,G.vexsi

11、.name); for(j=0;jG.vexnum;j+) printf(%20s,G.); for(k=0;kG.vexnum;k+) printf( %-5d,Djk); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) printf( %8s %8d %8sn,G.,Dij,G.vexsi.routersj); 5 設(shè)計(jì)過(guò)程中遇到的問(wèn)題：開(kāi)始時(shí)，設(shè)計(jì)思路一直停留在弗洛伊德算法中，這是我們數(shù)據(jù)結(jié)構(gòu)課程中介紹的求最短距離算法，輸入節(jié)點(diǎn)信息后，由程序自動(dòng)加入n個(gè)節(jié)點(diǎn)進(jìn)行試探（對(duì)任意兩個(gè)節(jié)點(diǎn)，它們之間的最短距離必然經(jīng)過(guò)

12、n個(gè)中間節(jié)點(diǎn)，0nN），一有更短距離則進(jìn)行更新并記錄，這也是動(dòng)態(tài)規(guī)劃的思想。但是實(shí)驗(yàn)要求動(dòng)態(tài)生成網(wǎng)絡(luò)拓?fù)鋱D，在老師的提醒下，我做了改進(jìn)。隨機(jī)生成頂點(diǎn)序號(hào)，若兩節(jié)點(diǎn)是鄰居節(jié)點(diǎn)，則讓兩節(jié)點(diǎn)進(jìn)行交換路由向量，再進(jìn)行更新。但是又出現(xiàn)了另一個(gè)問(wèn)題：無(wú)窮交換，因?yàn)樵谠O(shè)置循環(huán)交換條件時(shí)出現(xiàn)了問(wèn)題，于是記錄是否交換，若到達(dá)一定次數(shù)的交換都未成功更新路由表，則認(rèn)為路由表已穩(wěn)定，停止交換。但是通過(guò)多次試驗(yàn)，發(fā)現(xiàn)經(jīng)常在路由表還未穩(wěn)定時(shí)，循環(huán)就結(jié)束。究其原因，發(fā)現(xiàn)是“未更新的次數(shù)”這個(gè)標(biāo)記變量有隨機(jī)性，因?yàn)槎x這個(gè)變量時(shí)，是“從開(kāi)始交換，到交換到某個(gè)時(shí)刻，未更新的次數(shù)累加”。于是將這個(gè)變量改為“若連續(xù)n次隨機(jī)選取節(jié)點(diǎn)

13、進(jìn)行交換時(shí)，路由表都未更新，則視為bad交換，認(rèn)為路由表已穩(wěn)定，一旦有更新，則bad清0”。雖然采取這種方法，有時(shí)候也會(huì)出現(xiàn)提前結(jié)束，但是也是在極少情況下，比如隨機(jī)選取節(jié)點(diǎn)時(shí)一直選擇重復(fù)節(jié)點(diǎn)，為避免這個(gè)問(wèn)題，使用srand()函數(shù)產(chǎn)生隨機(jī)數(shù)種子，防止偽隨機(jī)數(shù)。問(wèn)題得到極大改善 六源程序清單#include#include#include#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define MAX

14、_NAME 9/頂點(diǎn)名稱(chēng)字符串最大長(zhǎng)度+1#define INFINITY 1000/用1000代替#define MAX_VERTEX_NUM 26 /最大頂點(diǎn)個(gè)數(shù)typedef int Status;typedef int Boolean;typedef int VRType;/定義頂點(diǎn)關(guān)系類(lèi)型為整型，與INFINITY的類(lèi)型一致typedef char PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_VERTEX_NUM;/三維數(shù)組typedef VRType DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/二維數(shù)

15、組 typedef struct /邊(弧)信息結(jié)構(gòu)VRType adj;/頂點(diǎn)關(guān)系類(lèi)型，對(duì)帶權(quán)圖，表示權(quán)值 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/二維數(shù)組 enum GraphKindDG,DN,UDG,UDN ;/有向圖、無(wú)向網(wǎng)、無(wú)向圖、無(wú)向網(wǎng)struct VertexType/最簡(jiǎn)單的頂點(diǎn)信息類(lèi)型(只有頂點(diǎn)名稱(chēng))char nameMAX_NAME;/頂點(diǎn)名稱(chēng) char routersMAX_VERTEX_NUMMAX_NAME;/定義最短路徑中到目的節(jié)點(diǎn)的上一跳 ;struct MGraph/圖的結(jié)構(gòu)VertexType vexsM

16、AX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣(二維數(shù)組)int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind; /圖的種類(lèi)標(biāo)志 ;int stable=0;/到達(dá)穩(wěn)定前路由表交換次數(shù) void visit(VertexType ver)/訪問(wèn)頂點(diǎn)的函數(shù)printf(%s,);void input(VertexType &ver) /輸入頂點(diǎn)信息的函數(shù) scanf(%s,);int LocateVex(MGraph G,VertexType u)/查找頂點(diǎn)u,并返回其位置int i;for(i=0;iG.vexnum;+i)if

17、(strcm,G.)=0)return i;void CreateDN(MGraph &G)/構(gòu)造有向網(wǎng)G int i,j,k;VRType w;/頂點(diǎn)關(guān)系類(lèi)型 VertexType v1,v2; printf( 請(qǐng)輸入網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的節(jié)點(diǎn)數(shù)、弧數(shù)); scanf(%d %d,&G.vexnum,&G.arcnum); printf( 請(qǐng)輸入%d個(gè)頂點(diǎn)的值（名稱(chēng)小于%d個(gè)字符）：,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;i+)/構(gòu)造頂點(diǎn)向量 input(G.vexsi); /輸入節(jié)點(diǎn)名稱(chēng) for(i=0;iG.vexnum;i+)/初始化

18、二維鄰接矩陣 for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; printf( 請(qǐng)輸入%d條弧的弧尾 弧頭 權(quán)值：n,G.arcnum); for(k=0;k=G.vexnum|v0)exit(OVERFLOW);return G.vexsv;void Display(MGraph G)int i,j,k;printf( %d個(gè)頂點(diǎn)%d條弧的無(wú)向網(wǎng)。頂點(diǎn)依次是：,G.vexnum,G.arcnum);for(i=0;iG.vexnum;i+)visit(GetVex(G,i);printf(n 初 始 路 由 表 如 下(1000表示無(wú)窮遠(yuǎn)):n); p

19、rintf( );for(i=0;iG.vexnum;i+) printf(%-8s,G.); printf(n); for(j=0;jG.vexnum;j+) printf(%20s,G.); for(k=0;kG.vexnum;k+) printf( %-5d,G.arcsjk.adj); printf(n); void ShortestPath_Floyd(MGraph G,PathMatrix P,DistancMatrix D)/用Floyd算法隨機(jī)更新兩頂點(diǎn)間最短路徑、頂點(diǎn)路由表，若Pvwu為true，則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)i

20、nt u,v,w,i,j,k;int change=1;/路由表有無(wú)交換 int bad=1;/不好的交換 for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+)Dvw=G.arcsvw.adj;/頂點(diǎn)v到w的直接距離for(u=0;uG.vexnum;u+)Pvwu=FALSE;if(DvwINFINITY)/從V到W有直接路徑 strcpy(G.vexsv.routersw,G.);Pvwv=Pvww=TRUE; /由v到w的路徑經(jīng)過(guò)v和w兩點(diǎn) else strcpy(G.vexsv.routersw,-); srand(unsigned)

21、time(NULL);/產(chǎn)生隨機(jī)數(shù)種子，防止偽隨機(jī)數(shù) while(change=1) for(;bad20;)/連續(xù)20次隨機(jī)交換無(wú)更新，為壞的交換，則停止隨機(jī)交換 v=rand()%G.vexnum;w=rand()%G.vexnum;if(DvwINFINITY&v!=w) printf(%s節(jié)點(diǎn)向%s節(jié)點(diǎn)發(fā)送距離向量，,G.,G.); change=0; for(u=0;uG.vexnum;u+) if(DwuINFINITY&Dvw+DwuDvu)/從v經(jīng)u到w的一條路徑更短 Dvu=Dvw+Dwu;/更新最短距離 change=1; bad=0; /一有更新，則不是壞的交換 if(w!=u) strcpy(G.vexsv.routersu,G.);/記錄上一跳節(jié)點(diǎn)名稱(chēng) for(i=0;iG.vexnum;i+) Pvwi=Pvui|Puwi;/從v到w的路徑經(jīng)過(guò)從v到u和從u到w的所有路徑 /if /for u if(change=1) stable+; printf( %s 的 路 由 表 如 下：n,G.); printf( 目的節(jié)點(diǎn) 最短路徑 上一跳n);for(j=0;jG.vexnum;j+) printf( %8s %8d %8sn,G.,Dvj,