云南大学软件学院计算机网络原理实验七

1、精品文档实验七、Link States Algorithm 的实现序号：姓名： 学号：2016成绩1 .实验目的：通过编程模拟实现 LSA.2 .实验环境：VS.net软件开发平台，可以使用任何编程语言。3 .实验要求(1)求网络中任何两个结点之间的最短路径(网络中至少有4个节点)。(2)得到任何一个节点上的转发表。4 .实验内容、拓扑结构通过链路状态算法计算A点到其它各点的cost ,最终输出A的路由表。算法提示：Initialization:5 N' = u /*u is source node*/6 for all nodes j /* j is dest node*/7 if

2、j adjacent 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 N'14 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 pl

3、us cost from i to j */18 until all nodes in N'19 实验分析，回答下列问题(1)给出LSA算法的主要思想。LSA算法即链路状态选路算法，该算法中，网络拓扑 和所有的链路费用都是已知的。它的具体实现依据 Dijkstra 算法，其主要思想是计算从某节点(源节点，u) 到网络中所有其他节点的最短路径。其算法是迭代算法， 即经算法的第k次迭代后，可知道到k个目的节点的最低 费用路径，在在到所有目的节点的最低费用路径之中，这k条路径具有k个最低费用。(2)通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。截图：1选择D，IDEEd己

4、bl 口，k£+ codenijks-rrci-f=xe3 30 3o O r - O 37J o U: nW-'一二 J w I请入节点个敢；6* JtSD ;bJOtcod ebl or kc - 4-0己中口”代打水卡请输入起始节电：B|1标1”¥；刃 最低货用路径是； B->A 最低戏用：2II标位点I 龈低册用踏模虻二 B"-一C 最低省用刀U标”点：D最低Ml路性是二B>D最低,用空*牲*本申用申本*拿*! *本U标八点：E 展低刎新#也 B)D>E 送假费用：3口标节点；F 最低费用蹄行怂: B>D>E冲 最低泥

5、用：5* /*¥*>tr* 是否半技：着岩n：杏ID E7cod ebl ockc + codeVDiij Ictra.exeH标片点MQ出於用辞件是:)->A用低资用：1H标”总：B/低快出畸役是:J一空最低跋用N口标W点:CU>£1>C最低费用：2* * *"杯节由工 心低洪用珞稼足二)>E后低费用：1H标节点：F 龈低费用路铳是；>E>F限低费用;3I 11 | I r irai _ _ w _一川 .举* 军事辨苓多=迷京茅4wfC赛水军基本 是否辞续：y：是n：否通泽口用 D Fcrjfieblor ky *，r

6、od ?'. 丁 jkstra .户"诸前入起始节点 EH标节点：A最低费用路粕是;E>r>A莅低费用:2*将*W*半*率*x*x字*就养目标出点：R袅低费用珞心是：E一；：3案源求科水隼拿*惠拿*云*行林东H -最惬胜用路性是：E>C最低费用:1率*率相寿率事杆科率率*«t*« n标"点；d认低费用成产是:E>D证俄我用：1* *II标打点：F最低费用路先上;一 !最低费用二2*器辛*早辛辛"宰手与¥生共¥ 是古髓法：是n：/y1DEcodeblockc+_codeD ijksira. ew

7、e X诂输入起始恃点;FU标.点：A际低费用路径是:FE D A最低豌用：4H稀节点：B最低新用路佗是：FE>DB果低皆用二5* 我*4共驷中共杷中件即II标打点：匚最低费刖降轻是:F>E>C最低费月二3* *»*¥*¥隼半4H标恃点6域仙费用略桂是:F- JE->D取低苑用得* *杯城*¥ 城* 城*目标节点国款低费用相长是二F->E心低费用二？“神神貂神神轴率*”料宰率率是杏处级；：y：是n： PirDtesE returnpd 1 (0x1) esecution time : 1060.536 s ress any k

8、y to continue.转发表:A:目的地链路最低费用BA->B2CA->D->E->C3DA->D1EA->D->E2FA->D->E->F4B:目的地链路最低费用AB->A2CB->C3DB->D2EB->D->E3FB->D->E->F5C:目的地链路最低费用AC->E->D->A3BC->B3DC->E->D2EC->E1FC->E->F3D:目的地链路最低费用AD->A1BD->B2CD->E->

9、C2ED->E1FD->E->F3E:目的地链路最低费用AE->D->A2BE->D->B3CE->C1DE->D1FE->F2F:目的地链路最低费用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

10、 FALSE=0;const int TRUE=1;void createGraph(int *arcs,int &num)cout<<"请依次输入各点的各条路径的cost:"<<endl<<"(如果拓扑图中的顶点没有直接相连，则输入 1000)"<<endl;cout<<""<<endl;for (int i=0;i<num;i+) arcsi=new int num;for(int j=0;j<num;j+) cin>>arcs

11、ij;6欢在下载精品文档void initRoute(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,in

12、t RL,int vexnum)char temp;int v0;bool * visit=new bool vexnum;cout<<" 请输入起始节点： "cin>>temp;v0=(int)temp-65; /A 的 ASCII 码是 65 cout<<endl;if(v0>=vexnum)cout<<" 输入错误，请重新输入 "<<endl;cin>>v0;elsefor(int cnt=0;cnt<vexnum;cnt+)visitcnt=FALSE; /vis

13、it 临时存储已经求得的最短路径RLcnt=arcsv0cnt; if(RLcnt<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;updat

14、eRoute(Rk,Rv,k,vexnum);visit=NULL;void printRoute(int * R,int RL, int vNum) int q=0;for(int dest=0;dest<vNum;dest+)if(RLdest!=0)printf(" 目标节点 :%c n",dest+65);if (Rdest0=-1)cout<<" 最短路径不存在 !"<<endl;continue; elsecout<<" 最低费用路径是:"<<endl;for(int

15、j=0;j<vNum;j+)if(Rdestj!=-1) printf("%c",Rdestj+65);cout<<(Rdestj=dest?"n":"->"); elsebreak;8欢迎下载 。精品文档低费用:"<<RLdest<<endl; cout<<"cout<<"*"<<endl;int main() int vNum;cout<<" 请输入节点个数： "cin>

16、>vNum;while(vNum<0)cout<<" 输入个数错误！请重新输入： "cin>>vNum;cout<<""<<endl;cout<<"你输入的"<<vNum<<"个节点将按 0-"<<vNum-1<<"顺序组成的邻接矩阵存储权 值"<<endl;int * weight=new int * vNum;int * shortestRoute=new in

17、t * vNum;int * routeLen=new int vNum;createGraph(weight,vNum);cout<<""<<endl;char isExit='y'doinitRoute(shortestRoute,routeLen,vNum);Dijkstra(weight,shortestRoute ,routeLen,vNum);printRoute(shortestRoute,routeLen,vNum);cout<<" 是否继续 : y: 是 n: 否 "cin>&g

18、t;isExit;cout<<endl;if(isExit='n') break;while(isExit='y');return OK;10欢迎下载。精品文档欢迎您的下载,资料仅供套考!致力为企业和个人提供合同协议， 策划案计划书，学习资料等等打造全网一站式需求1欺速下载你输入的个节京将按05顺序组或附郊按拓仲存瓶杈值请依次输入各点的各条蹄舐的8注：代收布扑图中的原点没行行技相连.则输A10M1 1000 10002 1000 10003 1 50 1 10001000 11021000 5 1000 2方输入起始也良：1目标半改4 最低班用路径是:%>8 最低把用：2口林中点 易徒耨用路件是:息>D>E>C最怔龄用二3* 洋字 * *：!：*目标节点：D 最低凿H惘性贴二 A>D最低蚣Hl”* 卡* *!Mi*口林9出任最低出用路也是:A'D>E最低赞用二 *mnnK»*«*Hir)tn!* H标打点盾 最低价用储拜足:i -iT |C区低费用;4案*部*K