云南大學(xué)軟件學(xué)院計(jì)網(wǎng)實(shí)驗(yàn)

1、云南大學(xué)軟件學(xué)院實(shí)驗(yàn)報(bào)告課程：計(jì)算機(jī)網(wǎng)絡(luò)原理實(shí)驗(yàn)任課教師：姓名：學(xué)號：專業(yè)：成績：實(shí)驗(yàn)八、LinkStatesAlgorithm的實(shí)現(xiàn)1 .實(shí)驗(yàn)?zāi)康模和ㄟ^編程模擬實(shí)現(xiàn)LSA.2 .實(shí)驗(yàn)環(huán)境：VS.net軟件開發(fā)平臺，可以使用任何編程語言。3 .實(shí)驗(yàn)要求(1)求網(wǎng)絡(luò)中任何兩個結(jié)點(diǎn)之間的最短路徑(網(wǎng)絡(luò)中至少有4個節(jié)點(diǎn))。(2)得到任何一個節(jié)點(diǎn)上的轉(zhuǎn)發(fā)表。4.實(shí)驗(yàn)內(nèi)容、拓?fù)浣Y(jié)構(gòu)通過鏈路狀態(tài)算法計(jì)算A點(diǎn)到其它各點(diǎn)的cost,最終輸出A的路由表。# include<stdio.h># include<stdlib.h># definemaxlen10該處設(shè)置路徑最大值，表示不存在

2、該路線)# definelarge999/(typedefstructintvexnum;charvexsmaxlen;intarcsmaxlenmaxlen;graph;voidinit_graph(graph*g)/初始化圖inti=0,j=0;/根據(jù)題目此處將圖的節(jié)點(diǎn)數(shù)初始化為5個/經(jīng)過兩層循環(huán)將條路徑初始化為無窮大g->vexnum=5;for(i=0;i<5;i+)for(j=0;j<5;j+)g->arcsij=999;g->arcs01=7;g->arcs10=7;/將相鄰兩個節(jié)點(diǎn)的路徑初始化為其權(quán)值g->arcs04=1;g->a

3、rcs12=1;g->arcs40=1;g->arcs21=1;g->arcs23=2;g->arcs14=8;g->arcs34=2;g->vexs0='A'g->vexs1='B'g->vexs2='C'g->vexs3='D'g->vexs4='E'g->arcs32=2;g->arcs41=8;g->arcs43=2;/將節(jié)點(diǎn)值初始化voidshortpath_dijkstra(graphg)/尋找最短路徑intcostmaxle

4、nmaxlen;intdistmaxlen;intpathmaxlen;intsmaxlen;inti,j,v0,min,u;chare;printf("Inputthesourcepoint(AorBorCorDorE):"/costij:節(jié)點(diǎn)i到節(jié)點(diǎn)j的成本/disti:源節(jié)點(diǎn)到i節(jié)點(diǎn)的距離或者是成本/已經(jīng)經(jīng)過了的節(jié)點(diǎn)/如果si=1,那么i節(jié)點(diǎn)已經(jīng)納入最短路徑集合);/用戶輸入源節(jié)點(diǎn)scanf("%c",&e);switch(e)case'A'v0=0;break;case'B'v0=1;break;case&

5、#39;C'v0=2;break;case'D'v0=3;break;case'E':v0=4;break;for(i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)costij=g.arcsij;for(i=0;i<g.vexnum;i+)disti=costv0i;/初始化源節(jié)點(diǎn)到各個節(jié)點(diǎn)的成本，如果與源節(jié)點(diǎn)相鄰則成本為權(quán)值，否則為無窮大if(disti<large&&disti>0)pathi=v0;si=0;sv0=1;for(i=0;i<g.vexnum;i+)m

6、in=large;u=v0;for(j=0;j<g.vexnum;j+)if(sj=0&&distj<min)min=distj;u=j;su=1;for(j=0;j<g.vexnum;j+)if(sj=0&&distu+costuj<distj)distj=distu+costuj;pathj=u;printf("Output%cnn",e);for(i=0;i<g.vexnum;i+)if(si=1)u=i;while(u!=v0)printf("%c<-",g.vexsu);u=p

7、athu;printf("%c",g.vexsu);printf(":%dn",disti);elseprintf("%c<-%c:nopathn",g.vexsi,g.vexsv0);intmain()graphg；init_graph(&g);shortpath_dijkstra（g）;system（"pause"）;return0;從A點(diǎn)開始，尋找到其余各點(diǎn)的最短路徑截圖如下:4 .實(shí)驗(yàn)分析，回答下列問題（1）給出LSA算法的主要思想。1、路由器初始化（所有節(jié)點(diǎn)的）狀態(tài)記錄集參數(shù)，將它們的長度設(shè)

8、為“無窮大”，標(biāo)號設(shè)為“暫時”。2、路由器更新與源T節(jié)點(diǎn)直接相連的所有暫時性節(jié)點(diǎn)的狀態(tài)記錄集。3、路由器在所有的暫時性節(jié)點(diǎn)中選擇距離V1的權(quán)值最低的節(jié)點(diǎn)。這個節(jié)點(diǎn)將是新的T節(jié)點(diǎn)。4、如果這個節(jié)點(diǎn)不是V2（目的節(jié)點(diǎn)），路由器則返回到步驟5。5、如果節(jié)點(diǎn)是V2,路由器則向前回溯，將它的前序節(jié)點(diǎn)從狀態(tài)記錄集中提取出來，如此循環(huán)，直到提取到V1為止。這個節(jié)點(diǎn)列表便是從V1到V2的最佳路由。（2）通過圖表算出任何兩個節(jié)點(diǎn)之間的最短路徑，并給出每個節(jié)點(diǎn)上的轉(zhuǎn)發(fā)表。AB: A->E->D->C->B 最小成本為：6AD: A->E->D最小成本為：3BD:B->C->D最小成本為：3 BE:B->C->D->E最小成本為：5 CE:C->D->E最小成本為：4AC: A->E->D->C最小成本為：5AE: A->E最小成本為：1BC:B->C最小成本為1CD:C->D最小成本為：2DE:D->E最小成本為：2（如果是源節(jié)點(diǎn)與目的節(jié)點(diǎn)反過來則路反過來即可）各個節(jié)點(diǎn)的轉(zhuǎn)發(fā)表：目的地鏈