云南大學(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)康模和ㄟ^(guò)編程模擬實(shí)現(xiàn) lsa.2 .實(shí)驗(yàn)環(huán)境：vs.net軟件開(kāi)發(fā)平臺(tái)，可以使用任何編程語(yǔ)言。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)通過(guò)鏈路狀態(tài)算法計(jì)算a點(diǎn)到其它各點(diǎn)的cost ,最終輸出a的路由表。算法提示：initialization:5 n = u /*u is source node*/6 for all nodes j /* j is dest node*/7 if j adj

2、acent to u8 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

3、*/18 until all nodes in n19 實(shí)驗(yàn)分析，回答下列問(wèn)題(1)給出lsa算法的主要思想。lsa算法即鏈路狀態(tài)選路算法，該算法中，網(wǎng)絡(luò)拓?fù)?和所有的鏈路費(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)通過(guò)圖表算出任何兩個(gè)節(jié)點(diǎn)之間的最短路徑，并給出每個(gè)節(jié)點(diǎn)上的轉(zhuǎn)發(fā)表。截圖：1選擇d，ideed己bl 口，k+ codenijks-rrci-f=

4、xe3 30 3o o r - o 37j o u: nw-一二 j w i請(qǐng)入節(jié)點(diǎn)個(gè)敢；6* jtsd ;bjotcod ebl or kc - 4-0己中口”代打水卡請(qǐng)輸入起始節(jié)電：b|1標(biāo)1”；刃 最低貨用路徑是； b-a 最低戲用：2ii標(biāo)位點(diǎn)i 齦低冊(cè)用踏模虻二 b-一c 最低省用刀u標(biāo)”點(diǎn)：d最低ml路性是二bd最低,用空*牲*本申用申本*拿*! *本u標(biāo)八點(diǎn)：e 展低刎新#也 b)de 送假費(fèi)用：3口標(biāo)節(jié)點(diǎn)；f 最低費(fèi)用蹄行慫: bde沖 最低泥用：5* /*tr* 是否半技：著巖n：杏id e7cod ebl ockc + codevdiij ictra.exeh標(biāo)片點(diǎn)mq出於

5、用辭件是:)-a用低資用：1h標(biāo)”總：b/低快出畸役是:j一空最低跋用n口標(biāo)w點(diǎn):cu1c最低費(fèi)用：2* * *杯節(jié)由工 心低洪用珞稼足二)e后低費(fèi)用：1h標(biāo)節(jié)點(diǎn)：f 齦低費(fèi)用路銃是；ef限低費(fèi)用;3i 11 | i r irai _ _ w _一川 .舉* 軍事辨苓多=迷京茅4wfc賽水軍基本 是否辭續(xù)：y：是n：否通澤口用 d fcrjfieblor ky *，rod ?. 丁 jkstra .戶(hù)諸前入起始節(jié)點(diǎn) eh標(biāo)節(jié)點(diǎn)：a最低費(fèi)用路粕是;era蒞低費(fèi)用:2*將*w*半*率*x*x字*就養(yǎng)目標(biāo)出點(diǎn)：r裊低費(fèi)用珞心是：e一；：3案源求科水隼拿*惠拿*云*行林東h -最?lèi)軇儆寐沸允牵篹c最低

6、費(fèi)用:1率*率相壽率事桿科率率*t* n標(biāo)點(diǎn)；d認(rèn)低費(fèi)用成產(chǎn)是:ed證俄我用：1* *ii標(biāo)打點(diǎn)：f最低費(fèi)用路先上;一 !最低費(fèi)用二2*器辛*早辛辛宰手與生共 是古髓法：是n：/y1decodeblockc+_coded ijksira. ewe x詁輸入起始恃點(diǎn);fu標(biāo).點(diǎn)：a際低費(fèi)用路徑是:fe d a最低豌用：4h稀節(jié)點(diǎn)：b最低新用路佗是：fedb果低皆用二5* 我*4共駟中共杷中件即ii標(biāo)打點(diǎn)：匚最低費(fèi)刖降輕是:fec最低費(fèi)月二3* *隼半4h標(biāo)恃點(diǎn)6域仙費(fèi)用略桂是:f- je-d取低苑用得* *杯城* 城* 城*目標(biāo)節(jié)點(diǎn)國(guó)款低費(fèi)用相長(zhǎng)是二f-e心低費(fèi)用二？“神神貂神神軸率*”料宰率率

7、是杏處級(jí)；：y：是n： pirdtese returnpd 1 (0x1) esecution time : 1060.536 s ress any ky to continue.轉(zhuǎn)發(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-e-f3e:目的地鏈路最低費(fèi)用ae-d-a2be-d-b3ce-c1de-d

8、1fe-f2f:目的地鏈路最低費(fèi)用af-e-d-a4bf-e-d-b5cf-e-c3df-e-d3ef-e2源代碼:#include#includeusing namespace std;const int max=1000;const int ok=1;const int false=0;const int true=1;void creategraph(int *arcs,int &num)cout請(qǐng)依次輸入各點(diǎn)的各條路徑的cost:endl(如果拓?fù)鋱D中的頂點(diǎn)沒(méi)有直接相連，則輸入 1000)endl;coutendl;for (int i=0;inum;i+) arcsi=new int

9、 num;for(int j=0;jarcsij;6歡在下載精品文檔void initroute(int * r ,int rl,int vnum)for(int i=0;ivnum;i+)rli=max;ri=new intvnum;for(int j=0;jvnum;j+) rij=-1;void updateroute(int r1, int r2,int dest,int num)for(int i=0;inum;i+)r1i=r2i;for(int j=0;jnum;j+)if (r1j=-1)r1j=dest; break;void dijkstra(int * arcs,int

10、* r,int rl,int vexnum)char temp;int v0;bool * visit=new bool vexnum;couttemp;v0=(int)temp-65; /a 的 ascii 碼是 65 cout=vexnum)cout 輸入錯(cuò)誤，請(qǐng)重新輸入 v0;elsefor(int cnt=0;cntvexnum;cnt+)visitcnt=false; /visit 臨時(shí)存儲(chǔ)已經(jīng)求得的最短路徑rlcnt=arcsv0cnt; if(rlcntmax) rcnt0=v0;rcnt1=cnt;rlv0=0;visitv0=true;for(int i=1;ivexnum;

11、i+) int min=max;int v=v0;for(int j=0;jvexnum;j+)if(!visitj)if(rljmin)v=j;min=rlj;visitv=true;for(int k=0;kvexnum;k+)if(!visitk&(min+arcsvkrlk)rlk=min+arcsvk;updateroute(rk,rv,k,vexnum);visit=null;void printroute(int * r,int rl, int vnum) int q=0;for(int dest=0;destvnum;dest+)if(rldest!=0)printf( 目標(biāo)節(jié)

12、點(diǎn) :%c n,dest+65);if (rdest0=-1)cout 最短路徑不存在 !endl;continue; elsecout 最低費(fèi)用路徑是:endl;for(int j=0;jvnum;j+)if(rdestj!=-1) printf(%c,rdestj+65);cout); elsebreak;8歡迎下載 。精品文檔低費(fèi)用:rldestendl; coutcout*endl;int main() int vnum;coutvnum;while(vnum0)coutvnum;coutendl;cout你輸入的vnum個(gè)節(jié)點(diǎn)將按 0-vnum-1順序組成的鄰接矩陣存儲(chǔ)權(quán) 值endl

13、;int * weight=new int * vnum;int * shortestroute=new int * vnum;int * routelen=new int vnum;creategraph(weight,vnum);coutendl;char isexit=y;doinitroute(shortestroute,routelen,vnum);dijkstra(weight,shortestroute ,routelen,vnum);printroute(shortestroute,routelen,vnum);coutisexit;cout8 最低把用：2口林中點(diǎn) 易徒耨用路件是:息dec最怔齡用二3* 洋字 * *：!：*目標(biāo)節(jié)點(diǎn)：d 最低鑿h惘性貼二 ad最低蚣hl”* 卡* *!mi*口林9出任最低出用路也是:ade最低贊用二 *mnnk*hir)tn!* h標(biāo)打點(diǎn)盾 最低價(jià)用儲(chǔ)拜足:i -it |c區(qū)低費(fèi)用;4案*部*kx *x *率=-=：；：=7= 是否雎續(xù)：丁是nd；g 造幽*dexed 的1 g4+ + codevdi