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

2、ent to u 5 then D(j) = c(u,j) 6 else D(j) = 7 8 Loop 9 find i not in N such that D(i) is a minimum 10 add i to N 11 update D(j) for all j adjacent to i and not in N : 12 D(j) = min( D(j), D(i) + c(i,j) ) 13 /* new cost to j is either old cost to j or known 14 shortest path cost to i plus cost from i

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

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

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

6、為,即已訪問的*/ pk+1=s;/*將頂點(diǎn)s加入到p數(shù)組中*/ Path(g,i,j,k+1); visiteds=0;/*重置訪問標(biāo)志位為，以便該頂點(diǎn)能被重新使用*/ s+; void Display(MGraph g,int i,int j)int k; p0=i; for(k=0;k,);/*依次輸出路徑中的節(jié)點(diǎn)*/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，且is*/ printf(n從%s到%s的最短路徑是:n,g.vex

7、,); printf(%s-,); Path2(g,path1,i,v0);/*調(diào)用ppath函數(shù)，輸出路徑中的節(jié)點(diǎn)*/ printf(%s ,); printf(路徑長(zhǎng)度：%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置空*/

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

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

10、*在網(wǎng)中找到其編號(hào)與輸入的出發(fā)景點(diǎn)的編號(hào)相同的頂點(diǎn)*/ for(int l=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/*在網(wǎng)中找到其編號(hào)與輸入的目地景點(diǎn)的編號(hào)相同的頂點(diǎn)*/ Dijkstra(g,i,j);/*調(diào)用Dijkstra函數(shù),用來輸出兩個(gè)景點(diǎn)間的最短路徑*/void main()int i=0,j=0;int b5=1,2,3,4,5;/*整型數(shù)組,用來給每個(gè)頂點(diǎn)的編號(hào)進(jìn)行賦值*/char *c5=A,B,C,D,E;/*字符串指針數(shù)組,用來給每個(gè)頂點(diǎn)的名稱進(jìn)行賦值*/ MGraph g;/*定義一個(gè)MGraph類型的變量g,用來創(chuàng)建一個(gè)無向網(wǎng)*/

11、 /*建立一個(gè)無向網(wǎng)，并用無向網(wǎng)表示節(jié)點(diǎn)的平面圖*/ int A55= /*用INF表示對(duì)應(yīng)頂點(diǎn)間沒有直達(dá)的路徑，用其它整型變量表示對(duì)應(yīng)頂點(diǎn)間有直達(dá)的路徑，且路徑的長(zhǎng)度就是該整型變量的值*/ 0,7,INF,INF,1, 7,0,1,INF,8, INF,1,0,2,INF, INF,INF,2,0,2, 1,8,INF,2,0 ; g.vexnum=5;/*網(wǎng)中頂點(diǎn)的個(gè)數(shù)為*/ g.arcnum=6;/*網(wǎng)中邊的個(gè)數(shù)為*/ for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.edgesij=Aij;/*建立無向網(wǎng)的鄰接矩陣*/ for(i=0;ig.v

12、exnum;i+) g.vexsi.num=bi;/*給每個(gè)節(jié)點(diǎn)一個(gè)編號(hào)*/ strcpy(,ci);/*通過字符串復(fù)制函數(shù)給每個(gè)節(jié)點(diǎn)一個(gè)名稱*/ int select;/*定義一個(gè)整型變量,用來輸入不同的選擇*/ do/*可提供循環(huán)輸入選擇,當(dāng)輸入的選擇為時(shí),退出循環(huán)*/ printf(n1.求節(jié)點(diǎn)間的最短路徑0.退出); printf(n請(qǐng)選擇操作:); scanf(%d,&select); switch(select) /*判斷select的值，根據(jù)其值跳轉(zhuǎn)到相應(yīng)的子模塊繼續(xù)執(zhí)行*/ case 1: Search(g);/*節(jié)點(diǎn)間的最短路徑*/ break; case 0:/*退出程序*/ break; while(select!=0);/*當(dāng)s