云南大學(xué)軟件學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)原理實(shí)驗(yàn)七

1、 實(shí)驗(yàn)七、Link States Algorithm的實(shí)現(xiàn)序號(hào)： 姓名： 學(xué)號(hào)： 2016 成績(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)ABDCE232111F2535通過鏈路狀態(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 nod

2、e*/4 if j adjacent 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 p

3、ath cost to i plus cost from i to j */ 15 until all nodes in N' 4實(shí)驗(yàn)分析，回答下列問題（1）給出LSA算法的主要思想。LSA算法即鏈路狀態(tài)選路算法，該算法中，網(wǎng)絡(luò)拓?fù)浜退械逆溌焚M(fèi)用都是已知的。它的具體實(shí)現(xiàn)依據(jù)Dijkstra算法，其主要思想是計(jì)算從某節(jié)點(diǎn)（源節(jié)點(diǎn)，u）到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的最短路徑。其算法是迭代算法，即經(jīng)算法的第k次迭代后，可知道到k個(gè)目的節(jié)點(diǎn)的最低費(fèi)用路徑，在在到所有目的節(jié)點(diǎn)的最低費(fèi)用路徑之中，這k條路徑具有k個(gè)最低費(fèi)用。（2）通過圖表算出任何兩個(gè)節(jié)點(diǎn)之間的最短路徑，并給出每個(gè)節(jié)點(diǎn)上的轉(zhuǎn)發(fā)表。截圖：轉(zhuǎn)

4、發(fā)表：A:目的地鏈路最低費(fèi)用BA->B2CA->D->E->C3DA->D1EA->D->E2FA->D->E->F4B：目的地鏈路最低費(fèi)用AB->A2CB->C3DB->D2EB->D->E3FB->D->E->F5C:目的地鏈路最低費(fèi)用AC->E->D->A3BC->B3DC->E->D2EC->E1FC->E->F3D:目的地鏈路最低費(fèi)用AD->A1BD->B2CD->E->C2ED->E1FD-&

5、gt;E->F3E:目的地鏈路最低費(fèi)用AE->D->A2BE->D->B3CE->C1DE->D1FE->F2F:目的地鏈路最低費(fèi)用AF->E->D->A4BF->E->D->B5CF->E->C3DF->E->D3EF->E2源代碼：#include<iostream>#include<stdio.h>using namespace std;const int MAX=1000;const int OK=1;const int FALSE=0;const

6、int TRUE=1;void createGraph(int *arcs,int &num)cout<<"請(qǐng)依次輸入各點(diǎn)的各條路徑的cost:"<<endl<<"(如果拓?fù)鋱D中的頂點(diǎn)沒有直接相連，則輸入1000)"<<endl;cout<<"-"<<endl;for (int i=0;i<num;i+)arcsi=new int num;for(int j=0;j<num;j+)cin>>arcsij;void initRoute

7、(int * R ,int RL,int vNum)for(int i=0;i<vNum;i+)RLi=MAX;Ri=new intvNum;for(int j=0;j<vNum;j+)Rij=-1;void updateRoute(int R1, int R2,int dest,int num)for(int i=0;i<num;i+)R1i=R2i;for(int j=0;j<num;j+)if (R1j=-1)R1j=dest;break;void Dijkstra(int * arcs,int * R,int RL,int vexnum)char temp;in

8、t v0;bool * visit=new bool vexnum;cout<<"請(qǐng)輸入起始節(jié)點(diǎn)："cin>>temp;v0=(int)temp-65; /A的ASCII碼是65cout<<endl;if(v0>=vexnum)cout<<"輸入錯(cuò)誤，請(qǐng)重新輸入"<<endl;cin>>v0;elsefor(int cnt=0;cnt<vexnum;cnt+)visitcnt=FALSE; /visit臨時(shí)存儲(chǔ)已經(jīng)求得的最短路徑RLcnt=arcsv0cnt;if(RLc

9、nt<MAX)Rcnt0=v0;Rcnt1=cnt;RLv0=0;visitv0=TRUE;for(int i=1;i<vexnum;i+)int min=MAX;int v=v0;for(int j=0;j<vexnum;j+)if(!visitj)if(RLj<min)v=j;min=RLj;visitv=TRUE;for(int k=0;k<vexnum;k+)if(!visitk&&(min+arcsvk<RLk)RLk=min+arcsvk;updateRoute(Rk,Rv,k,vexnum); visit=NULL;void p

10、rintRoute(int * R,int RL, int vNum)int q=0;for(int dest=0;dest<vNum;dest+)if(RLdest!=0)printf("目標(biāo)節(jié)點(diǎn) :%c n",dest+65);if (Rdest0=-1)cout<<"最短路徑不存在!"<<endl;continue;elsecout<<"最低費(fèi)用路徑是:"<<endl;for(int j=0;j<vNum;j+)if(Rdestj!=-1)printf("%c

11、",Rdestj+65);cout<<(Rdestj=dest?"n":"->");elsebreak;cout<<"最低費(fèi)用:"<<RLdest<<endl; cout<<"*"<<endl;int main()int vNum;cout<<"請(qǐng)輸入節(jié)點(diǎn)個(gè)數(shù)："cin>>vNum;while(vNum<0)cout<<"輸入個(gè)數(shù)錯(cuò)誤！請(qǐng)重新輸入："

12、;cin>>vNum;cout<<"-"<<endl;cout<<"你輸入的"<<vNum<<"個(gè)節(jié)點(diǎn)將按0-"<<vNum-1<<"順序組成的鄰接矩陣存儲(chǔ)權(quán)值"<<endl;int * weight=new int * vNum;int * shortestRoute=new int * vNum;int * routeLen=new int vNum;createGraph(weight,vNum);cout<<"-"<<endl;char isExit='y'doinitRoute(shortestRoute,routeLen,vNum);Dijkstra(weight,shortestRou