計算機網(wǎng)絡(luò)原理試驗八、Link-States-Algorithm的實現(xiàn)

1、的實現(xiàn)實驗八、Link States Algorithm序號：姓名：學(xué)號：成績1 .實驗?zāi)康模和ㄟ^編程模擬實現(xiàn) LSA.2 .實驗環(huán)境：VS.net軟件開發(fā)平臺，可以使用任何編程語言。3 .實驗要求4個節(jié)點)。(1)求網(wǎng)絡(luò)中任何兩個結(jié)點之間的最短路徑(網(wǎng)絡(luò)中至少有(2)得到任何一個節(jié)點上的轉(zhuǎn)發(fā)表。4 .實驗內(nèi)容、拓撲結(jié)構(gòu)A的路由表。通過鏈路狀態(tài)算法計算A點到其它各點的cost ,最終輸出算法提示：Initialization:5 N = u /*u is source node*/6 for all nodes j /* j is dest node*/7 if j adjacent to u

2、8 then D(j) = c(u,j)9 else D(j) =001011 Loop12 find i not in N such that D(i) is a minimum13 add i to N14 update D(j) for all j adjacent to i and not in N:15 D(j) = min( D(j), D(i) + c(i,j)16 /* new cost to j is either old cost to j or known17 shortest path cost to i plus cost from i to j */18 until

3、 all nodes in N4.實驗分析，回答下列問題(1)給出LSA算法的主要思想。答：LSA算法的主要思想為： 該算法用迭代算法， 其性質(zhì)是經(jīng)算法的第K次迭代后, 知道K個目的節(jié)點的最低費用路徑。A:鄰居節(jié)點發(fā)現(xiàn)與測試：各節(jié)點主動測試所有與之相鄰的節(jié)點的狀態(tài)。方法是周期性的向鄰, 居節(jié)點廣播簡短的查詢報文，通過接收鄰居節(jié)點的響應(yīng)報文, 來獲取與鄰居的狀態(tài)信息。B:鏈路狀態(tài)信息發(fā)布：根據(jù)收集到的狀態(tài)信息，構(gòu)造一個包含所有鄰居列表在 內(nèi)的分組LS,并通過洪泛法通告給算法作用區(qū)域內(nèi)的所有節(jié)點。C:路由選擇算法：收到 LS分組的節(jié)點，采用 Dijkstra 算法，為每個節(jié)點選擇 最短的路徑。(

4、2)通過圖表算出任何兩個節(jié)點之間的最短路徑，并給出每個節(jié)點上的轉(zhuǎn)發(fā)表。代碼：#include#include#define MAXV 20#define MAXSIZE 20#define MAXLEN 500#define INF 10000/*用表示8 */int a=0;typedef struct int num;char nameMAXSIZE;char contentMAXLEN; VertexType;typedef struct int edgesMAXVMAXV; int vexnum,arcnum;VertexType vexsMAXV; MGraph; int visit

5、edMAXV; int pMAXV;void Path(MGraph g,int i,int j,int k) /* 確定路徑上第k+1 個節(jié)點的編號*/int s;if(pk=j)/* 找到一條路徑*/ a+;/* 路徑的條數(shù)值加*/printf( 第 條:n,a); for(s=0;s,); printf(n); s=0; while(sg.vexnum) if(s!=i)/* 保證找到的是簡單路徑*/if(g.edgespks!=INF&visiteds=0)/* 當(dāng) vk 與 vs 之間有邊存在且vs 未被訪問過*/visiteds=1;/* 置訪問標志位為,

6、 即已訪問的*/pk+1=s;/* 將頂點 s 加入到 p 數(shù)組中 */Path(g,i,j,k+1);visiteds=0;/* 重置訪問標志位為，以便該頂點能被重新使用*/s+;void Display(MGraph g,int i,int j)int k;p0=i;for(k=0;k,);/*依次輸出路徑中的節(jié)點*/void Dispath(MGraph g,int dist,int path1,int s,int n,int v0,int i)if(si=1&i!=v0)/*當(dāng)V0不等于i ,且i C s*/printf(n從$到 s的最短路徑是：n,g.vex

7、,);printf(%s-,);Path2(g,path1,i,v0);/* 調(diào)用 ppath 函數(shù)，輸出路徑中的節(jié)點*/printf(%s ,);printf( 路徑長度：%dn,disti);void Dijkstra(MGraph g,int v0,int p)int distMAXV,path1MAXV;int sMAXV;int mindis,i,j,u,n=g.vexnum;for(i=0;in;i+)距離初始化*/disti=g.edgesv0i;/*/si=0;/*s置空 */if(g.e

8、dgesv0iINF)/* path1i=v0;elsepath1i=-1;sv0=1;path1v0=0;/* for(i=0;in;i+) mindis=INF;u=-1;for(j=0;jn;j+)/*路徑初始化*/源點編號v0 放入 s 中 */選取不在s 中具有最小距離的節(jié)點u*/if(sj=0&distjmindis) u=j;mindis=distj;su=1;/* 頂點 u 加入 s 中 */for(j=0;jn;j+)/* 修改不在s 中的節(jié)點的距離*/if(sj=0)if(g.edgesujINF&distu+g.edgesujdistj)/* 修正 disti,path1

9、i*/distj=distu+g.edgesuj;path1j=u;Dispath(g,dist,path1,s,n,v0,p);/*輸出最短路徑*/void Search(MGraph g)printf( 節(jié)點： n1.An2.Bn3.Cn4.Dn5.E);int i=0,j=0;char s=0;printf(nn 請選擇出發(fā)節(jié)點的編號：);scanf(%d,&i);printf( 請選擇目的節(jié)點的編號：);scanf(%d,&j);for(int k=0;kg.vexnum;k+)/*g.vexnum表示網(wǎng)中的頂點個數(shù)*/if(i=g.vexsk.num) i=k;/*在網(wǎng)中找到其編號與

10、輸入的出發(fā)景點的編號相同在網(wǎng)中找到其編號與輸入的目地景點的編號相同for(int l=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/*/Dijkstra(g,i,j);/* 調(diào)用 Dijkstra 函數(shù) , 用來輸出兩個景點間的最短路徑*/void main()int i=0,j=0;int b5=1,2,3,4,5;/* 整型數(shù)組, 用來給每個頂點的編號進行賦值*/char *c5=A,B,C,D,E;/*字符串指針數(shù)組, 用來給每個頂點的名稱進行賦值*/MGraph g;/*定義一個MGraph類型的變量g,用來創(chuàng)建一個無向網(wǎng)*/* 建立一個無向網(wǎng)，并用無向網(wǎng)表示節(jié)點的平面圖*/int A55=/* 用 INF 表示對應(yīng)頂點間沒有直達的路徑，用其它整型變量表示對應(yīng)頂點間有直達的路徑，且路徑的長度就是該整型變量的值*/0,7,INF,INF,1,7,0,1,INF,8,INF,1,0,2,INF,INF,INF,2,0,2,1,8